QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#317445#2433. Panda PreservelonelywolfAC ✓1331ms7620kbC++1421.1kb2024-01-29 00:43:582024-01-29 00:43:59

Judging History

你现在查看的是最新测评结果

  • [2024-01-29 00:43:59]
  • 评测
  • 测评结果:AC
  • 用时:1331ms
  • 内存:7620kb
  • [2024-01-29 00:43:58]
  • 提交

answer

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

#define int long long
using db = double;

const db eps = 1e-9;
const db pi = acos(-1);

mt19937 eng(time(0));
uniform_real_distribution<db> rd;

int sgn(db a) {
    if(a > eps) return 1;
    else if(a < -eps) return -1;
    else return 0;
}
// a < b : -1 | a == b : 0 | a > b : 1
int cmp(db a, db b) {
    return sgn(a - b);
}
// x in [a, b]
bool inmid(int x, int a, int b) {
    return sgn(x - a) * sgn(x - b) <= 0;
}

//点
struct point {
    db x, y;
    point operator + (const point &p) const {
        return {x + p.x, y + p.y};
    }
    point operator - (const point &p) const {
        return {x - p.x, y - p.y};
    }
    point operator * (db k) const {
        return {k * x , k * y};
    }
    point operator / (db k) const {
        return {x / k , y / k};
    }
    bool operator == (const point &p) const {
        return cmp(x, p.x) == 0 && cmp(y, p.y) == 0;
    }   
    // 优先比较 x 坐标
    bool operator < (const point &p) const {
        int t = cmp(x, p.x);
        if(t != 0) return t == -1;
        return cmp(y, p.y) == -1;
    }
    // 模长
    db len() {
        return sqrt(x * x + y * y);
    }
    // 模长平方
    db len2() {
        return x * x + y * y;
    }
    // 单位化(模长 > 0)
    point unit() {
        return (*this) / len();
    }
    // 极角 (-pi, pi]
    db getw() {
        return atan2(y, x);
    }
    // 逆时针旋转 k 弧度
    point rot(db k) {
        return {x * cos(k) - y * sin(k), x * sin(k) + y * cos(k)};
    }   
    // 逆时针旋转90°
    point rotleft() {
        return {-y, x};
    }
    // 将向量对称到 (-pi / 2, pi / 2] 半平面上
    point getdel() {
        if(sgn(x) == -1 || (sgn(x) == 0 && sgn(y) == -1)) {
            return (*this) * (-1);
        } else {
            return *this;
        }
    }
    // 判断在 y 轴上侧下侧 ( (-pi, 0] : 0 | (0, pi] : 1 )
    int getP() {
        return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) == -1);
    }
    friend istream &operator >> (istream &is, point &p) {
        return is >> p.x >> p.y;
    }
    friend ostream &operator << (ostream &os, point &p) {
        return os << p.x << " " << p.y;
    }
    
};

// 点与线段关系及交点

// 点 p 在点 a, b 构成的矩形中(包括边界)
bool inmid(point p, point a, point b) {
    return inmid(p.x, a.x, b.x) && inmid(p.y, a.y, b.y);
}
// 点积
db dot(point a, point b) {
    return a.x * b.x + a.y * b.y;
}
// 叉积
db cross(point a, point b) {
    return a.x * b.y - a.y * b.x;
}
// 从点 a 转到点 b 的方向角 (-pi, pi]
db rad(point a, point b) {
    return atan2(cross(a, b), dot(a, b));
}
// a b c (逆时针 : 1 | 顺时针 : -1 | 共线 : 0)
int clockwise(point a, point b, point c) {
    return sgn(cross(b - a, c - a));
}
// 按 (-pi, pi] 极角排序
bool cmpangle(point a, point b) {
    return a.getP() < b.getP() || (a.getP() == b.getP() && sgn(cross(a, b)) > 0);
}
// 点 p 在线段 ab 上
bool onS(point p, point a, point b) {
    return inmid(p, a, b) && sgn(cross(p - a, a - b)) == 0;
}
// 点 p 到直线 ab 的投影点
point proj(point p, point a, point b) {
    point k = b - a;
    return a + k * (dot(p - a, k) / k.len2());
}
// 点 p 关于直线 ab 的对称点
point reflect(point p, point a, point b) {
    return proj(p, a, b) * 2 - p;
}
// 判断直线 ab 和直线 cd 是否相交
bool checkLL(point a, point b, point c, point d) {
    return sgn(cross(b - a, d - c)) != 0;
}
// 求直线 ab 和直线 cd 的交点
point getLL(point a, point b, point c, point d) {
    db w1 = cross(a - c, d - c), w2 = cross(d - c, b - c);
    return (a * w2 + b * w1) / (w1 + w2);
}
// [l1, r1] 和 [l2, r2] 是否有交, 用于判断两线段是否相交
bool intersect(db l1, db r1, db l2, db r2) {
    if(l1 > r1) swap(l1, r1);
    if(l2 > r2) swap(l2, r2);
    return cmp(r1, l2) != -1 && cmp(r2, l1) != -1;
}
// 判断线段 ab 和线段 cd 是否相交(非严格相交)
bool checkSS(point a, point b, point c, point d) {
    return intersect(a.x, b.x, c.x, d.x) && intersect(a.y, b.y, c.y, d.y) && 
    sgn(cross(c - a, d - a) * cross(c - b, c - a)) <= 0 &&
    sgn(cross(a - c, b - c) * cross(a - d, b - d)) <= 0;
}
// 点 a 与 点 b 的距离
db dis(point a, point b) {
    return (b - a).len(); 
}
// 点 p 到直线 ab 的距离
db disLP(point p, point a, point b) {
    return fabs(cross(b - a, p - a)) / dis(a, b);
}
// 点 p 到线段 ab 的距离
db disSP(point p, point a, point b) {
    point q = proj(p, a, b);
    if(inmid(q, a, b)) return dis(p, q);
    else return min(dis(a, p), dis(b, p));
}
// 线段 ab 到 线段 cd 的距离
db disSS(point a, point b, point c, point d) {
    if(checkSS(a, b, c, d)) return 0;
    else return min({disSP(c, a, b), disSP(d, a, b), disSP(a, c, d), disSP(b, c, d)});
}

// 直线(有向) p[0] -> p[1]
struct line {
    point p[2];
    line (point a, point b) {
        p[0] = a, p[1] = b;
    }
    point& operator [] (int k) {
        return p[k];
    }
    // 点 q 位于直线左侧/半平面上 (严格 : > 0 | 不严格 : >= 0)
    bool include(point q) {
        return sgn(cross(p[1] - p[0], q - p[0])) > 0;
    }
    // 方向向量
    point dir() {
        return p[1] - p[0];
    }
    // 向左平移d, 默认为eps
    line push(db d = eps) {
        point delta = (p[1] - p[0]).rotleft().unit() * d;
        return {p[0] + delta, p[1] + delta};
    }
};
// 直线与直线的交点
point getLL(line l1, line l2) {
    return getLL(l1[0], l1[1], l2[0], l2[1]);
}
// 判断两直线是否平行
bool parallel(line l1, line l2) {
    return sgn(cross(l1.dir(), l2.dir())) == 0;
}
// 判断两直线是否平行且同向
bool sameDir(line l1, line l2) {
    return parallel(l1, l2) && sgn(dot(l1.dir(), l2.dir())) == 1;
}
// 同向则左侧小于右侧,否则按极角排序,用于半平面交
int operator < (line l1, line l2){
    if (sameDir(l1, l2)) return l2.include(l1[0]); 
    return cmpangle(l1.dir(), l2.dir());
}
// l3 半平面上是否包含 l1, l2 的交点, 用于半平面交
int checkpos(line l1, line l2, line l3) {
    return l3.include(getLL(l1, l2));
}
// 半平面交, 逆时针方向 (-pi, pi]
vector<line> getHL(vector<line> L) {
    sort(L.begin(), L.end());
    deque<line> q;
    for(int i = 0; i < (int)L.size(); i++) {
        if(i && sameDir(L[i], L[i-1])) continue;
        while(q.size() > 1 && !checkpos(q[q.size() -  2], q[q.size() - 1], L[i])) q.pop_back();
        while(q.size() > 1 && !checkpos(q[1], q[0], L[i])) q.pop_front();
        q.push_back(L[i]);
    }
    while(q.size() > 2 && !checkpos(q[q.size() -  2], q[q.size() - 1], q[0])) q.pop_back();
    while(q.size() > 2 && !checkpos(q[1], q[0], q[q.size() - 1])) q.pop_front();
    vector<line> ret;
    for(line l : q) {
        ret.push_back(l);
    }
    return ret;
}
// 最近点对 (A 需要先按 x 坐标排序), 答案为closepoint(A, 0, n - 1)
db closepoint(vector<point> &A, int l, int r) {
    if(r - l <= 5) {
        db ans = 1e20;
        for(int i = l; i <= r; i++) {
            for(int j = i + 1; j <= r; j++) {
                ans = min(ans, dis(A[i], A[j]));
            }
        }
        return ans;
    }
    int mid = (l + r) >> 1;
    db ans = min(closepoint(A, l, mid), closepoint(A, mid + 1, r));
    vector<point> B;
    for(int i = l; i <= r; i++) {
        if(abs(A[i].x - A[mid].x) <= ans) {
            B.push_back(A[i]);
        }
    }
    sort(B.begin(), B.end(), [](point a, point b) {
        return a.y < b.y;
    });
    for(int i = 0; i < B.size(); i++) {
        for(int j = i + 1; j < B.size() && B[j].y - B[i].y < ans; j++) {
            ans = min(ans, dis(B[i], B[j]));
        }
    }
    return ans;
}

// 圆 (o, r)
struct circle {
    point o;
    db r;
    // 点 p 是否在圆内 (1 : 圆内 | 0 : 圆上 | -1 : 圆外)
    int inside(point p) {
        return cmp(r, dis(o, p));
    }
};
// 两圆位置关系 (两圆公切线数量)
// 相离 : 4 | 外切 : 3 | 相交 : 2 | 内切 : 1 | 包含 : 0
int checkposCC(circle a, circle b) {
    if(cmp(a.r, b.r) == -1) swap(a, b);
    db d = dis(a.o, b.o);
    int w1 = cmp(d, a.r + b. r), w2 = cmp(d, a.r - b.r);
    if(w1 > 0) return 4;
    else if(w1 == 0) return 3;
    else if(w2 > 0) return 2;
    else if(w2 == 0) return 1;
    else return 0;
}
// 直线与圆的交点, 沿 a->b 的方向给出, 相切有两个
vector<point> getCL(circle c, point a, point b) {
    point k = proj(c.o, a, b);
    db d = c.r * c.r - (k - c.o).len2();
    if(sgn(d) == -1) return {};
    point del = (b - a).unit() * sqrt(max((db)0.0, d));
    return {k - del, k + del};
}
// 两圆交点, 沿圆 c1 逆时针方向给出 (c1, c2不能是同一个圆)
vector<point> getCC(circle c1, circle c2) {
    int pd = checkposCC(c1, c2);
    if(pd == 0 || pd == 4) return {};
    db a = (c2.o - c1.o).len2();
    db cosA = (c1.r * c1.r+ a - c2.r * c2.r) / (2 * c1.r * sqrt(max(a, (db)0.0)));
    db b = c1.r * cosA, c = sqrt(max((db)0.0, c1.r * c1.r - b * b));
    point k = (c2.o - c1.o).unit(), m = c1.o + k * b, del = k.rotleft() * c;
    if(pd == 1 || pd == 3) return {m};
    else return {m - del, m + del};
}
// 点到圆的切点, 沿圆 c 的逆时针方向给出 (未判相对关系)
vector<point> TangentCP(circle k, point p) {
    db a = (p - k.o).len(), b = k.r * k.r / a, c = sqrt(max((db)0.0, k.r * k.r - b * b));
    point t = (p - k.o).unit(), m = k.o + t * b, del = t.rotleft() * c;
    return {m - del, m + del};
}
// 外公切线 k1 切点 -> k2 切点 (k1 和 k2 切点相同时, l[0] 为切点)
// !!! 默认 k1.r > k2.r !!!
vector<line> TangentoutCC(circle k1, circle k2) {
    int pd = checkposCC(k1, k2);
    if(pd == 0) return {};
    else if (pd == 1) {
        point k = getCC(k1, k2)[0];
        return {{k, k + (k1.o - k2.o).rotleft()}};
    }
    if(cmp(k1.r, k2.r) == 0) {
        point del = (k2.o - k1.o).unit().rotleft().getdel();
        return {{k1.o - del * k2.r, k2.o - del * k2.r}, {k1.o + del * k1.r, k2.o + del * k2.r}};
    } else {
        point p = (k2.o * k1.r - k1.o * k2.r) / (k1.r - k2.r);
        vector<point> A = TangentCP(k1, p), B = TangentCP(k2, p);
        vector<line> ans;
        for(int i = 0; i < A.size(); i++) {
            ans.push_back({A[i], B[i]});
        }
        return ans;
    }
}
// 内公切线 k1 切点 -> k2 切点 (k1 和 k2 切点相同时, l[0] 为切点)
// !!! 默认 k1.r > k2.r !!!
vector<line> TangentinCC(circle k1, circle k2) {
    int pd = checkposCC(k1, k2);
    if(pd <= 2) return {};
    if(pd == 3) {
        point k = getCC(k1, k2)[0];
        return {{k, k + (k1.o - k2.o).rotleft()}};
    }
    point p = (k2.o * k1.r + k1.o * k2.r) / (k1.r + k2.r);
    vector<point> A = TangentCP(k1, p), B = TangentCP(k2, p);
    vector<line> ans;
    for(int i = 0; i < A.size(); i++) {
        ans.push_back({A[i], B[i]});
    }
    return ans;
}
// 所有公切线
vector<line> TangentCC(circle k1, circle k2) {
    bool flag = false;
    if(k1.r < k2.r) {
        swap(k1, k2);
        flag = true;
    }
    vector<line> A = TangentoutCC(k1, k2), B = TangentinCC(k1, k2);
    for(line k : B) A.push_back(k);
    if(flag) {
        for(line &k : A) {
            swap(k[0], k[1]);
        }
    }
    return A;
}
// 圆 c 与三角形 c.o a b 的有向面积交
db getarea(circle c, point a, point b) {
    point k = c.o;
    c.o = c.o - k;
    a = a - k, b = b - k;
    int pd1 = c.inside(a), pd2 = c.inside(b);
    vector<point> A = getCL(c, a, b);
    if(pd1 >= 0) {
        if(pd2 >= 0) return cross(a, b) / 2;
        return c.r * c.r * rad(A[1], b) / 2 + cross(a, A[1]) / 2;
    } else if (pd2 >= 0) {
        return c.r * c.r * rad(a, A[0]) / 2 + cross(A[0], b) / 2;
    } else {
        int pd = cmp(c.r, disSP(c.o, a, b));
        if(pd <= 0) {
            return c.r * c.r * rad(a, b) / 2;
        }
        return cross(A[0], A[1]) / 2 + c.r * c.r * (rad(a, A[0]) + rad(A[1], b)) / 2;
    }
} 
// 多边形与圆面积交
db getarea(vector<point> A, circle c) {
    int n = A.size();
    if(n <= 2) return 0;
    A.push_back(A[0]);
    db ans = 0;
    for(int i = 0; i < n; i++) {
        point a = A[i], b = A[i + 1];
        ans += getarea(c, a, b);
    }
    return fabs(ans);
}
// 三角形外接圆
circle getcircle(point a, point b, point c) {
    db a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;
    db a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;
    db d = a1 * b2 - a2 * b1;
    point o = {a.x + (c1 * b2 - c2 * b1) / d, a.y + (a1 * c2 - a2 * c1) /d};
    return {o, dis(o, a)};
}
// 最小圆覆盖
circle getScircle(vector<point> A) {
    shuffle(A.begin(), A.end(), eng);
    circle ans = {A[0], 0};
    for(int i = 1; i < A.size(); i++) {
        if(ans.inside(A[i]) == -1) {
            ans = {A[i], 0};
            for(int j = 0; j < i; j++) {
                if(ans.inside(A[j]) == -1) {
                    ans.o = (A[i] + A[j]) / 2;
                    ans.r = dis(ans.o, A[i]);
                    for(int k = 0; k < j; k++) {
                        if(ans.inside(A[k]) == -1) {
                            ans = getcircle(A[i], A[j], A[k]);
                        }    
                    }
                }
            }
        }
    }
    return ans;
}

// 反演

// 不经过反演中心的圆, 反演后变成另一个不经过反演中心的圆
circle invC2C(point O, double R, circle a) {
    db l1 = (a.o - O).len();
    db rb = (R * R * a.r) / (l1 * l1 - a.r * a.r);
    db l2 = l1 * rb / a.r;
    point b = O + (a.o - O) * (l2 / l1);
    return {b, rb};
}
// 经过反演中心的圆, 反演后变成不经过反演中心的直线
vector<point> invC2L(point O, double R, circle a) {
    db d = R * R / (2 * a.r);
    point k1 = O + (a.o - O).unit() * d;
    point k2 = k1 + (a.o - O).rotleft();
    return {k1, k2};
}
// 不经过反演中心的直线, 反演后变成经过反演中心的圆
circle invL2C(point O, double R, point k1, point k2) {
    db r = R * R / (2 * disLP(O, k1, k2));
    point o = (proj(O, k1, k2) - O).unit() * r + O;
    return {o, r};  
}

// 多边形

// 多边形有向面积
db area(vector<point> A) {
    db ans = 0;
    for(int i = 0; i < A.size(); i++) {
        ans += cross(A[i], A[(i + 1) % A.size()]);
    }
    return ans / 2;
}
// 判断是否是逆时针凸包
bool checkconvex(vector<point> A) {
    int n = A.size();
    if(n <= 2) return false;
    A.push_back(A[0]), A.push_back(A[1]);
    for(int i = 0; i < n; i++) {
        if(sgn(cross(A[i + 1] - A[i], A[i + 2] - A[i])) == -1) return false;
    }
    return true;
}
// 点与简单多边形的位置关系 (2 : 内部 | 1 : 边界 | 0 : 外部)
int contain(vector<point>A,point q) {
    int pd=0; A.push_back(A[0]);
    for (int i=1;i<A.size();i++){
        point u=A[i-1],v=A[i];
        if (onS(u,v,q)) return 1; if (cmp(u.y,v.y)>0) swap(u,v);
        if (cmp(u.y,q.y)>=0||cmp(v.y,q.y)<0) continue;
        if (sgn(cross(u-v,q-v))<0) pd^=1;
    }
    return pd<<1;
}
// 求凸包 (flag = 0 : 不严格 | flag = 1 : 严格)
vector<point> ConvexHull(vector<point> A, int flag = 1) {
    int n = A.size();
    if(n == 1) return A;
    if(n == 2) {
        if(A[0] == A[1]) return {A[0]};
        else return A;
    }
    vector<point> ans(2 * n);
    sort(A.begin(), A.end());
    int now = -1;
    for(int i = 0; i < A.size(); i++) {
        while(now > 0 && sgn(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag) now--;
        ans[++now] = A[i];
    }
    int pre = now;
    for(int i = n - 2; i >= 0; i--) {
        while(now > pre && sgn(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag) now--;
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}
// 凸包直径
db convexDiameter(vector<point> A) {
    int n = A.size();
    if(n == 2) {
        return dis(A[0], A[1]);
    }
    int now = 0;
    db ans = 0;
    for(int i = 0; i < n; i++) {
        while(true) {
            db s1 = cross(A[(i + 1) % n] - A[i], A[now] - A[i]);
            db s2 = cross(A[(i + 1) % n] - A[i], A[(now + 1) % n] - A[i]);
            if(cmp(s1, s2) <= 0) {
                now = (now + 1) % n;
            } else {
                ans = max({ans, dis(A[now], A[i]), dis(A[now], A[(i + 1) % n])});
                break;
            }
        }
    }
    return ans;
}
// 直线切凸包, 保留直线逆时针的所有点
vector<point> convexcut(vector<point> A, point k1, point k2) {
    int n = A.size();
    A.push_back(A[0]);
    vector<point> ans;
    for(int i = 0; i < n; i++) {
        int w1 = clockwise(k1, k2, A[i]), w2 = clockwise(k1, k2, A[i + 1]);
        if(w1 >= 0) ans.push_back(A[i]);
        if(w1 * w2 < 0) ans.push_back(getLL(k1, k2, A[i], A[i + 1]));
    }
    return ans;
}
// 多边形与直线是否严格相交
bool checkPos(vector<point> A, point k1, point k2) {
    struct ins {
        point m, u, v;
        bool operator < (const ins& k) const {
            return m < k.m;
        }
    };
    vector<ins> B;
    vector<point> poly = A;
    A.push_back(A[0]);
    for(int i = 1; i < A.size(); i++) {
        if(!checkLL(A[i - 1], A[i], k1, k2)) continue;
        point m = getLL(A[i - 1], A[i], k1, k2);
        if(inmid(m, A[i - 1], A[i])) {
            B.push_back({m, A[i - 1], A[i]});
        }
    }
    if(B.size() == 0) return false;
    sort(B.begin(), B.end());
    int now = 1;
    while(now < B.size() && B[now].m == B[now].m) now++;
    if(now == B.size()) return false;
    int flag = contain(poly, (B[0].m + B[now].m) / 2);
    if(flag == 2) return true;
    point d = B[now].m - B[0].m;
    for(int i = now; i < B.size(); i++) {
        if(!(B[i].m == B[i - 1].m) && flag == 2) return true;
        int tag = sgn(cross(B[i].v - B[i].u, B[i].m + d - B[i].u));
        if(B[i].m == B[i].u || B[i].m == B[i].v) flag += tag;
        else flag += tag * 2;
    }
    return flag == 2;
}
// 快速检查线段与多边形是否严格相交
bool checkinp(point r, point l, point m) {
    if(cmpangle(l, r)) return cmpangle(l, m) && cmpangle(m, r);
    return cmpangle(l, m) || cmpangle(m, r);
}
bool checkPosFast(vector<point> A, point k1, point k2) {
    if(contain(A, k1) || contain(A, k2)) return true;
    if(k1 == k2) return false;
    A.push_back(A[0]), A.push_back(A[1]);
    for(int i = 1; i < A.size(); i++) {
        if(!checkLL(A[i - 1], A[i], k1, k2)) continue;
        point now = getLL(A[i - 1], A[i], k1, k2);
        if((!inmid(now, A[i - 1], A[i])) || (!inmid(now, k1, k2))) continue;
        if(now == A[i]) {
            if(A[i] == k2) continue;
            point pre = A[i - 1], ne = A[i + 1];
            if(checkinp(pre - now, ne - now, k2 - now)) return true;
        } else if(now == k1) {
            if(k1 == A[i - 1] || k1 == A[i]) continue;
            if(checkinp(A[i - 1] - k1, A[i] - k1, k2 - k1)) return true;
        } else if(now == k2 || now == A[i - 1]) continue;
        else return true;
    }
    return false;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<point> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    db ans = 0;
    for (int i = 0; i < n; i++) {
        vector<line> L;
        L.push_back((line) {(point) {1e9, 1e9}, (point) {-1e9, 1e9}});
        L.push_back((line) {(point) {-1e9, 1e9}, (point) {-1e9, -1e9}});
        L.push_back((line) {(point) {-1e9, -1e9}, (point) {1e9, -1e9}});
        L.push_back((line) {(point) {1e9, -1e9}, (point) {1e9, 1e9}});
        for (int j = 0; j < n; j++) {
            if (i == j) 
                continue;
            point mid = (A[i] + A[j]) / 2;
            point v = (A[j] - A[i]).rotleft();
            L.push_back({mid, mid + v});
        }
        L = getHL(L);
        vector<point> v;
        for (int j = 0; j < L.size(); j++) {
            if (checkLL(L[j][0], L[j][1], L[(j + 1) % L.size()][0], L[(j + 1) % L.size()][1])) {
                point c = getLL(L[j], L[(j + 1) % L.size()]);
                if (contain(A, c) == 2) {
                    v.push_back(c);
                }
            }
        }
        for (line l : L) {
            for (int j = 0; j < n; j++) {
                point p1 = A[j], p2 = A[(j + 1) % n];
                if (checkLL(p1, p2, l[0], l[1])) {
                    point c = getLL(p1, p2, l[0], l[1]);
                    if (inmid(c, p1, p2)) {
                        v.push_back(c);
                    }
                }
            }
        }
        for (point p : v) {
            bool ok = 1;
            for (line l : L) {
                if (sgn(cross(l[1] - l[0], p - l[0])) < 0) {
                    ok = 0;
                    break;
                }
            }
            if (ok) {
                // cerr << dis(p, A[i]) << " ";
                ans = max(ans, dis(p, A[i]));
            }
        }
    }
    cout << fixed << setprecision(9) << ans << "\n";
    return 0;
}

Details

Test #1:

score: 100
Accepted
time: 1ms
memory: 3964kb

Test #2:

score: 0
Accepted
time: 1ms
memory: 3996kb

Test #3:

score: 0
Accepted
time: 1ms
memory: 3960kb

Test #4:

score: 0
Accepted
time: 1ms
memory: 3988kb

Test #5:

score: 0
Accepted
time: 1ms
memory: 3996kb

Test #6:

score: 0
Accepted
time: 1ms
memory: 3992kb

Test #7:

score: 0
Accepted
time: 0ms
memory: 3988kb

Test #8:

score: 0
Accepted
time: 1ms
memory: 3972kb

Test #9:

score: 0
Accepted
time: 0ms
memory: 3988kb

Test #10:

score: 0
Accepted
time: 1ms
memory: 3964kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 4036kb

Test #12:

score: 0
Accepted
time: 0ms
memory: 4004kb

Test #13:

score: 0
Accepted
time: 1ms
memory: 3916kb

Test #14:

score: 0
Accepted
time: 0ms
memory: 3944kb

Test #15:

score: 0
Accepted
time: 0ms
memory: 3964kb

Test #16:

score: 0
Accepted
time: 1ms
memory: 4048kb

Test #17:

score: 0
Accepted
time: 0ms
memory: 3980kb

Test #18:

score: 0
Accepted
time: 0ms
memory: 3976kb

Test #19:

score: 0
Accepted
time: 1ms
memory: 4036kb

Test #20:

score: 0
Accepted
time: 1ms
memory: 3992kb

Test #21:

score: 0
Accepted
time: 0ms
memory: 3964kb

Test #22:

score: 0
Accepted
time: 0ms
memory: 3988kb

Test #23:

score: 0
Accepted
time: 0ms
memory: 3928kb

Test #24:

score: 0
Accepted
time: 0ms
memory: 3932kb

Test #25:

score: 0
Accepted
time: 0ms
memory: 3960kb

Test #26:

score: 0
Accepted
time: 1ms
memory: 3944kb

Test #27:

score: 0
Accepted
time: 1ms
memory: 3996kb

Test #28:

score: 0
Accepted
time: 0ms
memory: 3992kb

Test #29:

score: 0
Accepted
time: 0ms
memory: 3988kb

Test #30:

score: 0
Accepted
time: 0ms
memory: 3984kb

Test #31:

score: 0
Accepted
time: 0ms
memory: 4048kb

Test #32:

score: 0
Accepted
time: 0ms
memory: 4040kb

Test #33:

score: 0
Accepted
time: 1ms
memory: 3972kb

Test #34:

score: 0
Accepted
time: 0ms
memory: 3964kb

Test #35:

score: 0
Accepted
time: 0ms
memory: 3932kb

Test #36:

score: 0
Accepted
time: 1ms
memory: 4004kb

Test #37:

score: 0
Accepted
time: 1ms
memory: 3968kb

Test #38:

score: 0
Accepted
time: 0ms
memory: 3972kb

Test #39:

score: 0
Accepted
time: 0ms
memory: 3996kb

Test #40:

score: 0
Accepted
time: 1ms
memory: 4004kb

Test #41:

score: 0
Accepted
time: 1ms
memory: 4052kb

Test #42:

score: 0
Accepted
time: 0ms
memory: 3964kb

Test #43:

score: 0
Accepted
time: 0ms
memory: 3984kb

Test #44:

score: 0
Accepted
time: 1ms
memory: 3940kb

Test #45:

score: 0
Accepted
time: 1ms
memory: 3964kb

Test #46:

score: 0
Accepted
time: 0ms
memory: 4000kb

Test #47:

score: 0
Accepted
time: 0ms
memory: 3964kb

Test #48:

score: 0
Accepted
time: 0ms
memory: 4004kb

Test #49:

score: 0
Accepted
time: 1ms
memory: 4048kb

Test #50:

score: 0
Accepted
time: 0ms
memory: 3988kb

Test #51:

score: 0
Accepted
time: 1ms
memory: 4044kb

Test #52:

score: 0
Accepted
time: 2ms
memory: 4056kb

Test #53:

score: 0
Accepted
time: 36ms
memory: 3976kb

Test #54:

score: 0
Accepted
time: 155ms
memory: 4108kb

Test #55:

score: 0
Accepted
time: 3ms
memory: 4056kb

Test #56:

score: 0
Accepted
time: 58ms
memory: 3968kb

Test #57:

score: 0
Accepted
time: 242ms
memory: 4104kb

Test #58:

score: 0
Accepted
time: 3ms
memory: 3996kb

Test #59:

score: 0
Accepted
time: 76ms
memory: 4080kb

Test #60:

score: 0
Accepted
time: 287ms
memory: 4064kb

Test #61:

score: 0
Accepted
time: 2ms
memory: 4100kb

Test #62:

score: 0
Accepted
time: 39ms
memory: 5064kb

Test #63:

score: 0
Accepted
time: 189ms
memory: 7620kb

Test #64:

score: 0
Accepted
time: 0ms
memory: 3980kb

Test #65:

score: 0
Accepted
time: 1ms
memory: 4000kb

Test #66:

score: 0
Accepted
time: 0ms
memory: 3988kb

Test #67:

score: 0
Accepted
time: 0ms
memory: 3984kb

Test #68:

score: 0
Accepted
time: 636ms
memory: 4172kb

Test #69:

score: 0
Accepted
time: 0ms
memory: 3872kb

Test #70:

score: 0
Accepted
time: 633ms
memory: 4144kb

Test #71:

score: 0
Accepted
time: 38ms
memory: 4020kb

Test #72:

score: 0
Accepted
time: 520ms
memory: 4184kb

Test #73:

score: 0
Accepted
time: 97ms
memory: 4164kb

Test #74:

score: 0
Accepted
time: 577ms
memory: 4188kb

Test #75:

score: 0
Accepted
time: 135ms
memory: 4048kb

Test #76:

score: 0
Accepted
time: 9ms
memory: 4076kb

Test #77:

score: 0
Accepted
time: 9ms
memory: 3960kb

Test #78:

score: 0
Accepted
time: 9ms
memory: 4016kb

Test #79:

score: 0
Accepted
time: 6ms
memory: 3972kb

Test #80:

score: 0
Accepted
time: 9ms
memory: 4064kb

Test #81:

score: 0
Accepted
time: 11ms
memory: 3992kb

Test #82:

score: 0
Accepted
time: 7ms
memory: 4064kb

Test #83:

score: 0
Accepted
time: 6ms
memory: 4016kb

Test #84:

score: 0
Accepted
time: 6ms
memory: 4024kb

Test #85:

score: 0
Accepted
time: 10ms
memory: 4068kb

Test #86:

score: 0
Accepted
time: 9ms
memory: 4028kb

Test #87:

score: 0
Accepted
time: 9ms
memory: 3992kb

Test #88:

score: 0
Accepted
time: 9ms
memory: 4016kb

Test #89:

score: 0
Accepted
time: 9ms
memory: 3928kb

Test #90:

score: 0
Accepted
time: 9ms
memory: 3932kb

Test #91:

score: 0
Accepted
time: 6ms
memory: 3984kb

Test #92:

score: 0
Accepted
time: 752ms
memory: 4208kb

Test #93:

score: 0
Accepted
time: 704ms
memory: 4172kb

Test #94:

score: 0
Accepted
time: 2ms
memory: 4000kb

Test #95:

score: 0
Accepted
time: 3ms
memory: 3992kb

Test #96:

score: 0
Accepted
time: 7ms
memory: 3936kb

Test #97:

score: 0
Accepted
time: 6ms
memory: 4016kb

Test #98:

score: 0
Accepted
time: 1201ms
memory: 4100kb

Test #99:

score: 0
Accepted
time: 1331ms
memory: 4072kb

Test #100:

score: 0
Accepted
time: 1244ms
memory: 4080kb

Test #101:

score: 0
Accepted
time: 1225ms
memory: 4148kb

Test #102:

score: 0
Accepted
time: 1177ms
memory: 4156kb

Test #103:

score: 0
Accepted
time: 825ms
memory: 4156kb

Test #104:

score: 0
Accepted
time: 1165ms
memory: 4108kb