QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380850#2433. Panda Preserve8BQube#AC ✓2246ms4312kbC++207.3kb2024-04-07 13:26:072024-04-07 13:26:07

Judging History

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

  • [2024-04-07 13:26:07]
  • 评测
  • 测评结果:AC
  • 用时:2246ms
  • 内存:4312kb
  • [2024-04-07 13:26:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

#define double long double

typedef pair<double, double> pdd;
typedef pair<pll, pll> Line;
const double eps = 1e-8;

pll operator+(const pll &a, const pll &b) { return pll(a.X + b.X, a.Y + b.Y); }
pdd operator+(const pdd &a, const pdd &b) { return pdd(a.X + b.X, a.Y + b.Y); }
pll operator-(const pll &a, const pll &b) { return pll(a.X - b.X, a.Y - b.Y); }
pdd operator-(const pdd &a, const pdd &b) { return pdd(a.X - b.X, a.Y - b.Y); }
pll operator*(const pll &a, const ll &b) { return pll(a.X * b, a.Y * b); }
pdd operator*(const pdd &a, const double &b) { return pdd(a.X * b, a.Y * b); }
pll operator/(const pll &a, const ll &b) { return pll(a.X / b, a.Y / b); }
pdd operator/(const pll &a, const double &b) { return pdd(a.X / b, a.Y / b); }
pdd operator/(const pdd &a, const double &b) { return pdd(a.X / b, a.Y / b); }
template<class T>
T dot(const pair<T, T> &a, const pair<T, T> &b) { return a.X * b.X + a.Y * b.Y; }
__int128 Ldot(const pll &a, const pll &b) { return (__int128)a.X * b.X + (__int128)a.Y * b.Y; }
template<class T>
T abs2(const pair<T, T> &a) { return dot(a, a); }
template<class T>
double abs(const pair<T, T> &a) { return sqrt(dot(a, a)); }
ll cross(const pll &a, const pll &b) { return a.X * b.Y - a.Y * b.X; }
double cross(const pdd &a, const pdd &b) { return a.X * b.Y - a.Y * b.X; }
__int128 Lcross(const pll &a, const pll &b) { return (__int128)a.X * b.Y - (__int128)a.Y * b.X; }
int sign(const ll &a) { return a == 0 ? 0 : a > 0 ? 1 : -1; }
int sign(const double &a) { return fabs(a) < eps ? 0 : a > 0 ? 1 : -1; }
int sign(const __int128 &a) { return a == 0 ? 0 : a > 0 ? 1 : -1; }
int ori(const pll &a, const pll &b, const pll &c) { return sign(cross(b - a, c - a)); }
int ori(const pdd &a, const pdd &b, const pdd &c) { return sign(cross(b - a, c - a)); }
int Lori(const pll &a, const pll &b, const pll &c) { return sign(Lcross(b - a, c - a)); }
bool btw(pll p1, pll p2, pll p3) {
    if (Lori(p1, p2, p3) != 0) return 0;
    return sign(Ldot(p1 - p3, p2 - p3)) <= 0;
}
bool btw(pdd p1, pdd p2, pdd p3) {
    if (ori(p1, p2, p3) != 0) return 0;
    return sign(dot(p1 - p3, p2 - p3)) <= 0;
}
pll perp(pll p1) { return pll(-p1.Y, p1.X); }

bool seg_intersect(pll p1, pll p2, pll p3, pll p4) {
    int a123 = Lori(p1, p2, p3);
    int a124 = Lori(p1, p2, p4);
    int a341 = Lori(p3, p4, p1);
    int a342 = Lori(p3, p4, p2);
    if (a123 == 0 && a124 == 0)
        return btw(p1, p2, p3) || btw(p1, p2, p4) || btw(p3, p4, p1) || btw(p3, p4, p2);
    return a123 * a124 <= 0 && a341 * a342 <= 0;
}

bool seg_intersect(pdd p1, pdd p2, pdd p3, pdd p4) {
    int a123 = ori(p1, p2, p3);
    int a124 = ori(p1, p2, p4);
    int a341 = ori(p3, p4, p1);
    int a342 = ori(p3, p4, p2);
    if (a123 == 0 && a124 == 0)
        return btw(p1, p2, p3) || btw(p1, p2, p4) || btw(p3, p4, p1) || btw(p3, p4, p2);
    return a123 * a124 <= 0 && a341 * a342 <= 0;
}

pdd intersect(pdd p1, pdd p2, pdd p3, pdd p4) {
    double a123 = cross(p2 - p1, p3 - p1);
    double a124 = cross(p2 - p1, p4 - p1);
    return (p4 * a123 - p3 * a124) / (a123 - a124);
}

pair<pll, ll> intersect(pll p1, pll p2, pll p3, pll p4) {
    ll a123 = cross(p2 - p1, p3 - p1);
    ll a124 = cross(p2 - p1, p4 - p1);
    if (a123 - a124 < 0) return make_pair(p3 * a124 - p4 * a123, a124 - a123);
    return make_pair(p4 * a123 - p3 * a124, a123 - a124);
}

int cmp(pll a, pll b, bool same = true) {
#define is_neg(k) (sign(k.Y) < 0 || (sign(k.Y) == 0 && sign(k.X) < 0))
    int A = is_neg(a), B = is_neg(b);
    if (A != B) return A < B;
    if (sign(cross(a, b)) == 0)
        return same ? abs2(a) < abs2(b) : -1;
    return sign(cross(a, b)) > 0;
}

pll area_pair(Line a, Line b) {
    return pll(cross(a.Y - a.X, b.X - a.X), cross(a.Y - a.X, b.Y - a.X));
}
bool isin(Line l0, Line l1, Line l2) {
    auto [a02X, a02Y] = area_pair(l0, l2);
    auto [a12X, a12Y] = area_pair(l1, l2);
    if (a12X - a12Y < 0) a12X *= -1, a12Y *= -1;
    return (__int128)a02Y * a12X - (__int128)a02X * a12Y > 0;
}
vector<Line> halfPlaneInter(vector<Line> arr) {
    sort(ALL(arr), [&](Line a, Line b) -> int {
        if (cmp(a.Y - a.X, b.Y - b.X, 0) != -1)
            return cmp(a.Y - a.X, b.Y - b.X, 0);
        return ori(a.X, a.Y, b.Y) < 0;
    });
    deque<Line> dq(1, arr[0]);
    auto pop_back = [&](int t, Line p) {
        while (SZ(dq) >= t && !isin(p, dq[SZ(dq) - 2], dq.back()))
            dq.pop_back();
    };
    auto pop_front = [&](int t, Line p) {
        while (SZ(dq) >= t && !isin(p, dq[0], dq[1]))
            dq.pop_front();
    };
    for (auto p : arr)
        if (cmp(dq.back().Y - dq.back().X, p.Y - p.X, 0) != -1)
            pop_back(2, p), pop_front(2, p), dq.pb(p);
    pop_back(3, dq[0]), pop_front(3, dq.back());
    return vector<Line>(ALL(dq));
}

const ll INF = 1e18;
const ll C = 20000;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<pll> poly(n);
    for (auto &[x, y] : poly)
        cin >> x >> y;
    for (auto &p : poly)
        p = p * 2;

    auto inpoly = [&](pll p, ll base) {
        for (int i = 0; i < n; ++i)
            if (btw(poly[i] * base, poly[(i + 1) % n] * base, p))
                return 1;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            cnt += seg_intersect(p, p + pll(1, INF), poly[i] * base, poly[(i + 1) % n] * base); 
        }
        return cnt & 1;
    };
    
    double ans = 0;

    auto check = [&](pair<pll, ll> p, pll q) {
        //cerr << "(b)check (" << p.X.X / (double)p.Y << ", " << p.X.Y / (double)p.Y << ")\n";
        if (!inpoly(p.X, p.Y)) return;
        pdd cur = p.X / (double)(p.Y);
        //cerr << "check (" << cur.X << ", " << cur.Y << ")\n";
        ans = max(ans, abs(cur - (pdd)q));
    };

    for (int i = 0; i < n; ++i) {
        vector<Line> vec;
        vec.pb(Line(pll(0, -C), pll(1, -C)));
        vec.pb(Line(pll(C, 0), pll(C, 1)));
        vec.pb(Line(pll(0, C), pll(-1, C)));
        vec.pb(Line(pll(-C, 0), pll(-C, -1)));
        for (int j = 0; j < n; ++j)
            if (i != j) {
                pll mid = poly[i] + poly[j];
                mid = mid / 2LL;
                vec.emplace_back(mid, mid + perp(poly[j] - poly[i])); 
            }
        vec = halfPlaneInter(vec);
        /*cerr << "(" << poly[i].X << ", " << poly[i].Y << "):\n";
        for (auto [a, b] : vec)
            cerr << "(" << a.X << ", " << a.Y << ")---(" << b.X << ", " << b.Y << ")\n";*/
        vector<pair<pll, ll>> convex;
        for (int j = 0; j < SZ(vec); ++j) {
            convex.pb(intersect(vec[j].X, vec[j].Y, vec[(j + 1) % SZ(vec)].X, vec[(j + 1) % SZ(vec)].Y));
            check(convex.back(), poly[i]);
        }
        for (int t = 0; t < SZ(convex); ++t) {
            auto [p, b1] = convex[t];
            auto [q, b2] = convex[(t + 1) % SZ(convex)];
            pdd a = p / (double)(b1), b = q / (double)(b2);
            for (int j = 0; j < n; ++j)
                if (seg_intersect(a, b, (pdd)poly[j], (pdd)poly[(j + 1) % n])) {
                    pdd c = intersect(a, b, (pdd)poly[j], (pdd)poly[(j + 1) % n]);
                    ans = max(ans, abs(c - (pdd)poly[i]));
                }
        }
    }

    cout << fixed << setprecision(20) << ans / 2 << "\n";
}

Details

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

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

Test #24:

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

Test #25:

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

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

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

Test #31:

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

Test #32:

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

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

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

Test #38:

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

Test #39:

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

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

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

Test #44:

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

Test #45:

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

Test #46:

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

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

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

Test #51:

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

Test #52:

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

Test #53:

score: 0
Accepted
time: 103ms
memory: 3904kb

Test #54:

score: 0
Accepted
time: 459ms
memory: 3956kb

Test #55:

score: 0
Accepted
time: 5ms
memory: 3908kb

Test #56:

score: 0
Accepted
time: 123ms
memory: 3904kb

Test #57:

score: 0
Accepted
time: 506ms
memory: 3948kb

Test #58:

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

Test #59:

score: 0
Accepted
time: 121ms
memory: 3892kb

Test #60:

score: 0
Accepted
time: 509ms
memory: 3952kb

Test #61:

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

Test #62:

score: 0
Accepted
time: 95ms
memory: 3904kb

Test #63:

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

Test #64:

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

Test #65:

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

Test #66:

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

Test #67:

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

Test #68:

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

Test #69:

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

Test #70:

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

Test #71:

score: 0
Accepted
time: 103ms
memory: 3840kb

Test #72:

score: 0
Accepted
time: 1583ms
memory: 4168kb

Test #73:

score: 0
Accepted
time: 292ms
memory: 4116kb

Test #74:

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

Test #75:

score: 0
Accepted
time: 344ms
memory: 4180kb

Test #76:

score: 0
Accepted
time: 14ms
memory: 4088kb

Test #77:

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

Test #78:

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

Test #79:

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

Test #80:

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

Test #81:

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

Test #82:

score: 0
Accepted
time: 16ms
memory: 3956kb

Test #83:

score: 0
Accepted
time: 17ms
memory: 3956kb

Test #84:

score: 0
Accepted
time: 15ms
memory: 3856kb

Test #85:

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

Test #86:

score: 0
Accepted
time: 15ms
memory: 3876kb

Test #87:

score: 0
Accepted
time: 15ms
memory: 3868kb

Test #88:

score: 0
Accepted
time: 16ms
memory: 3800kb

Test #89:

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

Test #90:

score: 0
Accepted
time: 15ms
memory: 3800kb

Test #91:

score: 0
Accepted
time: 16ms
memory: 3860kb

Test #92:

score: 0
Accepted
time: 1270ms
memory: 4312kb

Test #93:

score: 0
Accepted
time: 1216ms
memory: 4176kb

Test #94:

score: 0
Accepted
time: 4ms
memory: 4088kb

Test #95:

score: 0
Accepted
time: 5ms
memory: 3912kb

Test #96:

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

Test #97:

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

Test #98:

score: 0
Accepted
time: 2200ms
memory: 4240kb

Test #99:

score: 0
Accepted
time: 2236ms
memory: 4012kb

Test #100:

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

Test #101:

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

Test #102:

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

Test #103:

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

Test #104:

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