QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#723131#9434. Italian CuisineHaz_BegoniaWA 56ms3992kbC++2019.0kb2024-11-07 21:15:012024-11-07 21:15:01

Judging History

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

  • [2024-11-07 21:15:01]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:3992kb
  • [2024-11-07 21:15:01]
  • 提交

answer

//
// Created by 85228 on 2024/11/2.
//

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define fi first
#define se second

using PII = pair<int, int>;

const int N = 1E6 + 10, Mod = 998244353, INF = 1E18;

using db = long double;
#define pb push_back
#define all(x) (x).begin(), (x).end()
const db eps = 1e-8;
const db pi = acos(-1);
const db inf = 1e20;

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int sgn(db x) {
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    else return 1;
}

inline db sqr(db x) {
    return x * x;
}

struct Point {
    db x, y;

    Point() { x = y = 0; }

    Point(db _x, db _y) { x = _x, y = _y; }

    void input() {
        int _x, _y;
        cin >> _x >> _y;
        x = (db)_x, y = (db)_y;
//        cin >> x >> y;
    }

    friend inline bool operator==(Point A, Point B) { return sgn(A.x - B.x) == 0 && sgn(A.y - B.y) == 0; }

    friend inline bool operator<(Point A, Point B) { return sgn(A.x - B.x) == 0 ? sgn(A.y - B.y) < 0 : A.x < B.x; }

    friend inline Point operator-(Point A, Point B) { return Point(A.x - B.x, A.y - B.y); }

    friend inline Point operator+(Point A, Point B) { return Point(A.x + B.x, A.y + B.y); }

    friend inline Point operator*(Point A, db k) { return Point(A.x * k, A.y * k); }

    friend inline Point operator/(Point A, db k) { return Point(A.x / k, A.y / k); }

    friend inline db operator^(Point A, Point B) { return A.x * B.y - A.y * B.x; }

    friend inline db operator*(Point A, Point B) { return A.x * B.x + A.y * B.y; }

    inline db len2() { return x * x + y * y; }

    inline db len() { return sqrt(len2()); }

    inline db angle() { return atan2(y, x); }

    inline db rad(Point A, Point B) {
        // P.rad(A, B) -> PA, PB 直接的夹角
        Point P = *this;
        return fabs(atan2((A - P) ^ (B - P), (A - P) * (B - P)));
    }

    inline Point trunc(db r) {
        // 将 向量缩放至长度为 r
        db l = len();
        if (!sgn(l)) return *this;
        r /= l;
        return Point(x * r, y * r);
    }

    inline Point rotate_left() { return Point(-y, x); }

    inline Point rotate_right() { return Point(y, -x); }

    inline Point rotate(Point P, db ang) {
        //逆时针
        Point v = (*this) - P;
        db c = cos(ang), s = sin(ang);
        return Point(P.x + v.x * c - v.y * s, P.y + v.x * s + v.y * c);
    }

    inline Point rotate(db ang) {
        return rotate(Point(0, 0), ang);
    }
};

inline db area(Point A, Point B, Point C) {
    return fabs((A - B) ^ (C - B)) / 2;
}

struct Line {
    Point s, e;

    Line() {}

    Line(Point _s, Point _e) {
        s = _s;
        e = _e;
    }

    void input() {
        s.input();
        e.input();
    }

    void adjust() { if (e < s) swap(e, s); }

    friend inline bool operator==(Line A, Line B) { return A.s == B.s && A.e == B.e; }

    Line(Point p, db ang) {
        s = p;
        e = p + (sgn(ang - pi / 2) == 0 ? Point(0, 1) : Point(1, tan(ang)));
    }

    Line(db a, db b, db c) {
        // ax + by + c == 0 知道系数 a, b, c 推出 s, e
        if (sgn(a) == 0) s = Point(0, -c / b), e = Point(1, -c / b);
        else if (sgn(b) == 0) s = Point(-c / a, 0), e = Point(-c / a, 1);
        else s = Point(0, -c / b), e = Point(1, (-c - a) / b);
    }

    inline db len() { return (e - s).len(); }

    inline db angle2() { return atan2(e.y - s.y, e.x - s.x); }

    inline db angle() {
        //angle in [0, pi)
        db k = angle2();
        if (sgn(k) < 0) k += pi;
        if (sgn(k - pi) == 0) k -= pi;
        return k;
    }

    int relation(Point p) {
        // 1 点在直线左边
        // 2 点在直线右边
        // 3 点在直线上
        int c = sgn((p - s) ^ (e - s));
        return !c ? 3 : 1 + (c > 0);
    }

    bool PointOnSegment(Point p) {
        // 判断点在线段上
        // true 在线段上
        // false 不在线段上
        return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0;
    }

    bool parallel(Line v) {
        // 两直线是否平行(可能共线或重合)
        // true 平行
        // false 不平行
        return sgn((e - s) ^ (v.e - v.s)) == 0;
    }

    bool Line_collinear(Line v) {
        return sgn((e - s) ^ (v.e - e)) == 0 && sgn((e - s) ^ (v.e - s)) == 0;
    }

    int segcrossseg(Line v) {
        // 判断两条线段是否相交
        // 2 规范相交: 表示两条线段相交且相交点不在任何一条线段的端点上
        // 1 非规范相交; 表示两条线段相交,但相交点在至少一条线段的端点上
        // 0 不相交
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        int d3 = sgn((v.e - v.s) ^ (s - v.s));
        int d4 = sgn((v.e - v.s) ^ (e - v.s));
        if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)return 2;
        return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
               (d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
               (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
               (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
    }

    int linecrossseg(Line v) {
        // 用于判断线段和直线是否相交
        // 2 规范相交: 表示线段与直线相交且相交点不在线段的端点上
        // 1 非规范相交; 表示线段与直线相交,但相交点在线段的端点上
        // 0 不相交
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        if ((d1 ^ d2) == -2) return 2;
        return (d1 == 0 || d2 == 0);
    }

    int linecrossline(Line v) {
        // 判断两条直线是否相交
        // 0 平行
        // 1 重合
        // 2 相交
        if ((*this).parallel(v)) return v.relation(s) == 3;
        return 2;
    }

    Point Intersection(Line v) {
        // 两条直线的交点
        db a1 = (v.e - v.s) ^ (s - v.s);
        db a2 = (v.e - v.s) ^ (e - v.s);
        return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));
    }

    db dispointtoline(Point p) {
        //点到直线的距离
        return fabs((p - s) ^ (e - s)) / len();
    }

    db dispointtoseg(Point p) {
        // 点到一条线段的距离
        if(PointOnSegment(p)) {
            cout << "ok";
            return 0;
        }
        if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
            return min((p - s).len(), (p - e).len());
        return dispointtoline(p);
    }

    db dissegtoseg(Line v) {
        // 两条线段之间的最短距离
        // 前提是两条线段不相交, 因为如果它们相交, 最短距离就是 0
        return min(min(dispointtoseg(v.s), dispointtoseg(v.e)), min(v.dispointtoseg(s), v.dispointtoseg(e)));
    }

    Point lineprog(Point p) {
        // 点 p 在直线上的投影
        return s + (((e - s) * ((e - s) * (p - s))) / ((e - s).len2()));
    }

    Point symmetrypoint(Point p) {
        // 点 p 关于直线的对称点
        Point q = lineprog(p);
        return Point(2 * q.x - p.x, 2 * q.y - p.y);
    }

    Point progpointtoline(Point a) {
        // 点在直线上的投影
        Point a1 = e - s, a2 = a - s;
        db k = (a1 * a2) / a1.len2();
        return s + (e - s) * k;
    }
};

struct Circle {
    Point p;
    db r;

    Circle() {}

    Circle(Point p, db r) {
        this->p = p;
        this->r = r;
    }

    Circle(db x, db y, db r) {
        p = Point(x, y);
        this->r = r;
    }

    Circle(Point a, Point b, Point c, bool opt) {
        // 根据给定的点计算圆的中心和半径
        // opt: 0 外接圆 1 内切圆
        Line u, v;
        if (opt == 0) {
            u = Line((a + b) / 2, ((a + b) / 2) + ((b - a).rotate_left()));
            v = Line((b + c) / 2, ((b + c) / 2) + ((c - b).rotate_left()));
            p = u.Intersection(v);
            r = (p - a).len();
        } else {
            db m = atan2(b.y - a.y, b.x - a.x), n = atan2(c.y - a.y, c.x - a.x);
            u.s = a;
            u.e = u.s + Point(cos((n + m) / 2), sin((n + m) / 2));
            v.s = b;
            m = atan2(a.y - b.y, a.x - b.x), n = atan2(c.y - b.y, c.x - b.x);
            v.e = v.s + Point(cos((n + m) / 2), sin((n + m) / 2));
            p = u.Intersection(v);
            r = Line(a, b).dispointtoseg(p);
        }
    }

    friend inline bool operator==(Circle A, Circle B) { return A.p == B.p && sgn(A.r - B.r) == 0; }

    db area() { return pi * r * r; }

    db circumference() { return 2 * pi * r; }

    int relation(Point b) {
        // 判断一个点 b 相对于圆的位置
        // 0 圆外 1 圆上 2 圆内
        int opt = sgn((b - p).len() - r);
        return opt < 0 ? 2 : (opt == 0);
    }

    int relationseg(Line v) {
        // 线段 v 相对于圆的位置
        // 0 表示线段在圆外
        // 1 表示线段与圆相切
        // 2 表示线段与圆相交或完全在圆内
        int opt = sgn(v.dispointtoseg(p) - r);
        return opt < 0 ? 2 : (opt == 0);
    }

    int relationline(Line v) {
        // 直线 v 相对于圆的位置
        // 0 表示直线在圆外
        // 1 表示直线与圆相切
        // 2 表示直线与圆相交或完全在圆内
        int opt = sgn(v.dispointtoline(p) - r);
        return opt < 0 ? 2 : (opt == 0);
    }

    int relationcircle(Circle A) {
        // 判断两个圆之间的位置关系
        // 5 相离
        // 4 外切
        // 3 相交
        // 2 内切
        // 1 内含
        // Circle C1(Point(0, 0), 5);  // 圆C1, 圆心(0, 0), 半径5
        // Circle C2(Point(1, 1), 3);  // 圆C2, 圆心(1, 1), 半径3
        // C1.relationcircle(C2) 返回 1, C2 内含于 C1
        db d = (p - A.p).len();
        if (sgn(d - r - A.r) > 0) return 5;
        if (sgn(d - r - A.r) == 0) return 4;
        return 2 + sgn(d - fabs(r - A.r));
    }

    vector<Point> pointcrossline(Line v) {
        // 返回圆与直线的交点
        // 如果圆与直线相交, 则返回交点的坐标
        // 如果相切, 返回一个交点
        // 如果相离, 则返回空向量
        vector<Point> vec;
        vec.clear();
        if (!(*this).relationline(v)) return vec;
        Point a = v.lineprog(p);
        db d = v.dispointtoline(p);
        d = sqrt(r * r - d * d);
        if (sgn(d) == 0) vec.pb(a);
        else vec.pb(a + (v.e - v.s).trunc(d)), vec.pb(a - (v.e - v.s).trunc(d));
        return vec;
    }

    vector<Point> pointcrosscircle(Circle A) {
        // 计算两个圆的交点, 并返回这些交点的坐标
        // 注意不要两圆重合了
        vector<Point> vec;
        vec.clear();
        int t = relationcircle(A);
        if (t == 5 || t == 1) return vec;
        db d = (p - A.p).len();
        db l = (d * d + r * r - A.r * A.r) / (2. * d);
        db h = sqrt(r * r - l * l);
        Point q = p + (A.p - p).trunc(l);
        if (t == 2 || t == 4) {
            vec.pb(q);
            return vec;
        }
        vec.pb(q + ((A.p - p).rotate_left()).trunc(h));
        vec.pb(q + ((A.p - p).rotate_right()).trunc(h));
        return vec;
    }
};

inline Circle smallestcircle(vector<Point> p) {
    // 计算最小圆覆盖
    int n = p.size();
    random_shuffle(all(p));
    Circle C = Circle(p[0], 0.0);
    for (int i = 1; i < n; i++)
        if (C.relation(p[i]) == 0) {
            C = Circle(p[i], 0.0);
            for (int j = 0; j < i; j++)
                if (C.relation(p[j]) == 0) {
                    C = Circle((p[i] + p[j]) / 2, (p[i] - p[j]).len() / 2);
                    for (int k = 0; k < j; k++)
                        if (C.relation(p[k]) == 0)
                            C = Circle(p[i], p[j], p[k], 0);
                }
        }
    return C;
}

struct Polygon {
    int n;
    vector<Point> p;
    vector<Line> l;

    Polygon(int _n) {
        n = _n;
        p.assign(n, {});
        l.assign(n, {});
    }

    Polygon(vector<Point> a) {
        n = a.size();
        p = a;
        l.resize(n);
        for (int i = 0; i < n; i++) l[i] = Line(p[i], p[(i + 1) % n]);
    }

    db area() {
        // 计算多边形的面积
        db ans = 0;
        for (int i = 2; i < n; i++) ans += (p[i] - p[0]) ^ (p[i - 1] - p[0]);
        return fabs(ans) / 2;
    }

    db diameter() {
        // 旋转卡壳
        // 计算多边形的直径
        if (n == 2) {
            return (p[0] - p[1]).len();
        }
        int j = 2;
        db ans = 0;
        for (int i = 0; i < n; i++) {
            while (((p[(i + 1) % n] - p[i]) ^ (p[j] - p[i])) < ((p[(i + 1) % n] - p[i]) ^ (p[(j + 1) % n] - p[i])))
                j = (j + 1) % n;
            ans = max(ans, max((p[i] - p[j]).len(), (p[(i + 1) % n] - p[(j + 1) % n]).len()));
        }
        return ans;
    }

    int point_in_Polygon(Point P) {
        // 判断点是否在多边形内部
        // -1 在边界
        // 1 在内部
        // 0 不在内部
        for (auto i: l) {
            if(i.PointOnSegment(P)) return -1;
        }

        Point P1, P2;
        int flag = 0;
        for(int i = 0, j = n - 1; i < n; j = i++) {
            P1 = p[i];
            P2 = p[j];
            if ((sgn(P1.y - P.y) > 0 != sgn(P2.y - P.y) > 0) &&
                sgn(P.x - (P.y - P1.y) * (P1.x - P2.x) / (P1.y - P2.y) - P1.x) < 0)
                flag = !flag;
        }
        return flag;
    }

    void input() {
//        cin >> n;
        p.resize(n);
        l.resize(n);
        for (int i = 0; i < n; i++) {
            p[i].input();
        }
        for (int i = 0; i < n; i++) {
            l[i] = Line(p[i], p[(i + 1) % n]);
        }
    }
};

Polygon ConvexHull(vector<Point> a) {
    // Andrew 算法求凸包
    // 严格的凸包(即不存在三点共线),若非严格则将 <= 改成 <
    int n = a.size(), m = -1;
    vector<Point> p(n * 2);
    sort(all(a));
    // 下凸包
    for (int i = 0; i < n; i++) {
        for (; m > 0 && ((p[m] - p[m - 1]) ^ (a[i] - p[m - 1])) <= 0; m--);
        p[++m] = a[i];
    }
    if (n == 1) {
        return Polygon(a);
    }
    // 上凸包
    int k = m;
    for (int i = n - 2; i >= 0; i--) {
        for (; m > k && ((p[m] - p[m - 1]) ^ (a[i] - p[m - 1])) <= 0; m--);
        p[++m] = a[i];
    }
    p.resize(m);
    return Polygon(p);
}

Polygon ConvexHull(Polygon A) {
    return ConvexHull(A.p);
}

Polygon HalfPlanes(vector<Line> l) {
    // 半平面交, 多条线限制区域形成一个交集
    vector<Point> p;
    int n = l.size();
    auto cmp = [](Line A, Line B) {
        db r = A.angle2() - B.angle2();
        if (sgn(r) != 0) return sgn(r) < 0;
        return sgn((A.e - A.s) ^ (B.e - A.s)) < 0;
    };
    sort(all(l), cmp);
    vector<Line> q(n + 2);
    vector<Point> b(n + 2);
    int head = 0, tail = 0;
    q[0] = l[0];
    for (int i = 1; i < n; i++)
        if (sgn(l[i].angle2() - l[i - 1].angle2()) != 0) {
            if (head < tail && q[head].parallel(q[head + 1])) return Polygon(p);
            if (head < tail && q[tail].parallel(q[tail - 1])) return Polygon(p);
            while (head < tail && l[i].relation(b[tail - 1]) == 2) tail--;
            while (head < tail && l[i].relation(b[head]) == 2) head++;
            q[++tail] = l[i];
            if (head < tail) b[tail - 1] = q[tail].Intersection(q[tail - 1]);
        }
    while (head < tail && l[head].relation(b[tail - 1]) == 2) tail--;
    while (head < tail && l[tail].relation(b[head]) == 2) head++;
    if (tail - head <= 1) return Polygon(p);
    b[tail] = q[head].Intersection(q[tail]);
    p.resize(tail - head + 1);
    for (int i = head; i <= tail; i++) p[i - head] = b[i];
    return Polygon(p);
}

vector<Point> getminrectanglecover(vector<Point> a, int n) {
    if (n < 3) return vector<Point> ();
    db res = inf;
    int r1 = 1, r2 = 1, r3 = 1;
    a.push_back(a[0]);
    vector<Point> vp;
    for(int i = 0; i < n; i++) {
        while (sgn((a[i + 1] - a[i]) * (a[r1 + 1] - a[r1])) > 0)
            r1 = (r1 + 1) % n;
        while (sgn((a[i + 1] - a[i] ^ (a[r2 + 1] - a[i])) -
                   (a[i + 1] - a[i] ^ a[r2] - a[i])) >= 0)
            r2 = (r2 + 1) % n;
        if (i == 0) r3 = r2;
        while (sgn((a[i + 1] - a[i]) * (a[r3 + 1] - a[r3])) < 0)
            r3 = (r3 + 1) % n;
        Line li = Line(a[i], a[i + 1]);
        db area = li.dispointtoline(a[r2]) *
                  (li.progpointtoline(a[r1]) - li.progpointtoline(a[r3])).len();
        if (sgn(area - res) < 0) {
            res = area;
            vp.clear();
            vp.pb(li.progpointtoline(a[r1]));
            vp.pb(li.progpointtoline(a[r3]));
            Line lii = Line(a[r2], li.angle());
            vp.pb(lii.progpointtoline(a[r1]));
            vp.pb(lii.progpointtoline(a[r3]));
            Point mi = vp[0];
            for (auto j : vp) {
                mi = min(mi, j);
            }
            sort(vp.begin(), vp.end(), [&] (const Point &a, const Point &b) {
                auto p = mi;
                int x = sgn((a - p) ^ (b - p));
                if (x == 0) {
                    return sgn((a - p).len() - (b - p).len()) < 0;
                } else {
                    return x > 0;
                }
            });
        }
    }
    return vp;
}

void solve(int T) {
    int n, xc, yc, r;
    cin >> n >> xc >> yc >> r;
    Circle cir({(db)xc, (db)yc}, (db)r);
    Polygon p(n);
    p.input();
    if(T == 6665) {
        cout << n << ' ' << xc << ' ' << yc << ' ' << r << '\n';
        for(auto [x, y]: p.p) {
            cout << x << ' ' << y << '\n';
        }
    }
    int i = 0, j = 1;
    db ans = 0, S = 0;
    for(int cnt = 0; cnt < n; cnt++) {
        while(1) {
            int nj = (j + 1) % n;
            vector<Point> b = {p.p[i], p.p[j], p.p[nj]};
            Polygon c(b);
            if(c.point_in_Polygon(cir.p)) {
                break;
            }
            Line L1 = {p.p[i], p.p[nj]};
            Line L2 = {p.p[j], p.p[nj]};
            if(cir.relationseg(L1) < 1 && cir.relationseg(L2) < 1) {
                S += area(p.p[i], p.p[j], p.p[nj]);
                ans = max(ans, S);
                j = nj;
            } else {
                break;
            }
            if(i == j) {
                break;
            }
        }
        int ni = (i + 1) % n;
        S -= area(p.p[i], p.p[ni], p.p[j]);
        i = ni;
        if(i == j) {
            S = 0;
            j = (i + 1) % n;
        }
    }
    cout << (int)(ans * 2) << '\n';
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("E:\\C++clion\\in.txt", "r", stdin);
//    freopen("E:\\C++clion\\out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0), cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while(T--) {
        solve(T);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3656kb

input:

3
5
1 1 1
0 0
1 0
5 0
3 3
0 5
6
2 4 1
2 0
4 0
6 3
4 6
2 6
0 3
4
3 3 1
3 0
6 3
3 6
0 3

output:

5
24
0

result:

ok 3 number(s): "5 24 0"

Test #2:

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

input:

1
6
0 0 499999993
197878055 -535013568
696616963 -535013568
696616963 40162440
696616963 499999993
-499999993 499999993
-499999993 -535013568

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: -100
Wrong Answer
time: 56ms
memory: 3992kb

input:

6666
19
-142 -128 26
-172 -74
-188 -86
-199 -157
-200 -172
-199 -186
-195 -200
-175 -197
-161 -188
-144 -177
-127 -162
-107 -144
-90 -126
-87 -116
-86 -104
-89 -97
-108 -86
-125 -80
-142 -74
-162 -72
16
-161 -161 17
-165 -190
-157 -196
-154 -197
-144 -200
-132 -200
-128 -191
-120 -172
-123 -163
-138...

output:

19 -142 -128 26
-172 -74
-188 -86
-199 -157
-200 -172
-199 -186
-195 -200
-175 -197
-161 -188
-144 -177
-127 -162
-107 -144
-90 -126
-87 -116
-86 -104
-89 -97
-108 -86
-125 -80
-142 -74
-162 -72
5093
2862
2539
668
3535
7421
4883
5711
5624
1034
2479
3920
4372
2044
4996
5070
2251
4382
4175
1489
1154
3...

result:

wrong answer 1st numbers differ - expected: '5093', found: '19'