C++(clang++11) 解法, 执行用时: 468ms, 内存消耗: 1272K, 提交时间: 2021-05-09 21:23:59

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using namespace std;

typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;

template <typename T>
inline void read(T &f) {
    f = 0; T fu = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
    while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
    f *= fu;
}

template <typename T>
void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}

const int N = 1e5 + 5;

struct point_t {
    int x, y;
    point_t (int a = 0, int b = 0) : x(a), y(b) {}
} a[N];

point_t operator - (const point_t a, const point_t b) {
    return point_t(a.x - b.x, a.y - b.y);
}

long double ans = 1e50;
ll all, now;
int n;

ll cross(point_t a, point_t b) {
    return 1ll * a.x * b.y - 1ll * a.y * b.x;
}

ll area2(int i, int j, int k) {
    return abs(cross(a[j] - a[i], a[k] - a[i]));
}

long double cross(long double a, long double b, long double c, long double d) {
    return a * d - b * c;
}

void calc(int i, int j) {
    long double l, r;
    point_t vi = a[i % n + 1] - a[i], vj = a[j % n + 1] - a[j];
    ll ai = area2(i, i % n + 1, j);
    ll aj = area2(i % n + 1, j, j % n + 1);
    ll ij = area2(i, i % n + 1, j % n + 1);
    // fprintf(stderr, "ai = %lld, aj = %lld\n", ai, aj);
    if (now * 2 <= all) l = 0;
    else l = (long double)(now * 2 - all) / 2 / ai;
    if ((now - ai + aj) * 2 >= all) r = 1;
    else r = 1 - (long double)(all - (now - ai + aj) * 2) / 2 / ij;
    // fprintf(stderr, "now = %lld, l = %.10lf, r = %.10lf\n", now, (double)l, (double)r);
    auto calc = [&](long double pos) {
        long double x = a[i].x + pos * vi.x;
        long double y = a[i].y + pos * vi.y;
        long double _now = now - ai * pos;
        long double areaj = fabs(cross(a[j].x - x, a[j].y - y, a[j % n + 1].x - x, a[j % n + 1].y - y));
        long double k = (all - _now * 2) / 2 / areaj;
        long double _x = a[j].x + vj.x * k;
        long double _y = a[j].y + vj.y * k;
        return (x - _x) * (x - _x) + (y - _y) * (y - _y);
    };
    while (r - l > 1e-10) {
        long double mid1 = l + (r - l) / 3;
        long double mid2 = r - (r - l) / 3;
        if (calc(mid1) < calc(mid2)) r = mid2;
        else l = mid1;
    }
    ans = min(ans, calc((l + r) / 2));
    // fprintf(stderr, "i = %d, j = %d, l = %.10lf, r = %.10lf, calc = %.10lf\n", i, j, (double)l, (double)r, (double)calc((l + r) / 2));
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i].x), read(a[i].y);
    for (int i = 2; i < n; i++) all += area2(1, i, i + 1);
    for (int i = 1, j = 2; i <= n; ) {
        while ((now + area2(i, j, j % n + 1)) * 2 < all) {
            now += area2(i, j, j % n + 1);
            j = j % n + 1;
        }
        calc(i, j);
        if ((now + area2(i, j, j % n + 1) - area2(i, i % n + 1, j % n + 1)) * 2 > all) {
            now -= area2(i, i % n + 1, j);
            ++i;
        } else {
            now += area2(i, j, j % n + 1);
            j = j % n + 1;
        }
    }
    printf("%.10lf\n", (double)sqrt(ans));
    return 0;
}