Submission #1305831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305831		dashka	2circles (balkan11_2circles)	C++20	10 / 100	232 ms	4580 KiB

twocircles

#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-9;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(double t) const { return Point(x * t, y * t); }
    double cross(const Point& p) const { return x * p.y - y * p.x; }
    double len() const { return sqrt(x * x + y * y); }
    Point normalize() const { double l = len(); return Point(x / l, y / l); }
    Point perpLeft() const { return Point(-y, x); }
};

double dist(const Point& a, const Point& b) { return (a - b).len(); }

int n;
vector<Point> poly;
double originalArea;

double polygonArea(const vector<Point>& p) {
    double area = 0;
    int m = p.size();
    for (int i = 0; i < m; i++)
        area += p[i].cross(p[(i + 1) % m]);
    return area / 2.0;
}

bool lineIntersect(Point p1, Point d1, Point p2, Point d2, Point& res) {
    double denom = d1.cross(d2);
    if (abs(denom) < EPS) return false;
    double t = (p2 - p1).cross(d2) / denom;
    res = p1 + d1 * t;
    return true;
}

vector<Point> shrinkPolygon(double R) {
    int m = poly.size();
    if (m < 3) return {};
    
    vector<Point> shiftedP(m), shiftedD(m);
    
    for (int i = 0; i < m; i++) {
        Point a = poly[i];
        Point b = poly[(i + 1) % m];
        Point d = b - a;
        Point normal = d.perpLeft().normalize();
        shiftedP[i] = a + normal * R;
        shiftedD[i] = d;
    }
    
    vector<Point> result;
    for (int i = 0; i < m; i++) {
        int j = (i + 1) % m;
        Point inter;
        if (lineIntersect(shiftedP[i], shiftedD[i], shiftedP[j], shiftedD[j], inter)) {
            result.push_back(inter);
        }
    }
    
    if (result.size() < 3) return {};
    
    double area = polygonArea(result);
    if (area <= EPS || area >= originalArea - EPS) {
        return {};
    }
    
    return result;
}

// Rotating calipers - O(n) convex polygon diameter
double polygonDiameter(const vector<Point>& p) {
    int m = p.size();
    if (m < 2) return 0;
    if (m == 2) return dist(p[0], p[1]);
    
    // Find antipodal pairs using rotating calipers
    int j = 1;
    double maxDist = 0;
    
    for (int i = 0; i < m; i++) {
        Point edge = p[(i + 1) % m] - p[i];
        // Advance j while triangle area increases
        while (abs(edge.cross(p[(j + 1) % m] - p[i])) > abs(edge.cross(p[j] - p[i])) + EPS) {
            j = (j + 1) % m;
        }
        maxDist = max(maxDist, dist(p[i], p[j]));
        maxDist = max(maxDist, dist(p[(i + 1) % m], p[j]));
    }
    
    return maxDist;
}

bool canFit(double R) {
    vector<Point> shrunk = shrinkPolygon(R);
    if (shrunk.size() < 2) return false;
    return polygonDiameter(shrunk) >= 2.0 * R - EPS;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    poly.resize(n);
    for (int i = 0; i < n; i++)
        cin >> poly[i].x >> poly[i].y;
    
    originalArea = polygonArea(poly);
    
    double lo = 0, hi = 2e7;
    for (int iter = 0; iter < 100; iter++) {
        double mid = (lo + hi) / 2.0;
        if (canFit(mid)) lo = mid;
        else hi = mid;
    }
    
    cout << fixed << setprecision(3) << lo << endl;
    return 0;
}

• Subtask 1: 10 / 100