QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#166005#6850. Amazing spacecraftPPP#WA 68ms6812kbC++175.8kb2023-09-06 00:01:422023-09-06 00:01:42

Judging History

This is the latest submission verdict.

  • [2023-09-06 00:01:42]
  • Judged
  • Verdict: WA
  • Time: 68ms
  • Memory: 6812kb
  • [2023-09-06 00:01:42]
  • Submitted

answer

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
const int maxN = 3e4 + 10;
ll x[maxN], y[maxN];
ll px[maxN], py[maxN];
int m;
ll X, Y, R;
void upd(vector<pair<ll,ll>>& F) {
    int pos = min_element(F.begin(), F.end()) - F.begin();
    rotate(F.begin(), F.begin() + pos, F.end());
}
int tp(pair<ll,ll>& a) {
    if (a.first > 0 || (a.first == 0 && a.second > 0)) return -1;
    return 1;
}
bool cmp(pair<ll,ll>& a, pair<ll,ll>& b) {
    if (tp(a) != tp(b)) return tp(a) < tp(b);
    return (a.first * b.second > a.second * b.first);
}
ll area(pair<ll,ll>& a, pair<ll,ll>& b, pair<ll,ll>& c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
void solve() {
    cin >> n;
    vector<pair<ll,ll>> A, B;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        x[i] *= -1;
        y[i] *= -1;
        A.emplace_back(x[i], y[i]);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> px[i] >> py[i];
        B.emplace_back(px[i], py[i]);
    }
    cin >> X >> Y >> R;
    upd(A);
    upd(B);
    vector<pair<ll,ll>> fin;
    fin.emplace_back(A[0].first + B[0].first, A[0].second + B[0].second);
    vector<pair<ll,ll>> vecs;
    for (int i = 0; i < A.size(); i++) {
        vecs.emplace_back(A[(i + 1) % A.size()].first - A[i].first, A[(i + 1) % A.size()].second - A[i].second);
    }
    for (int i = 0; i < B.size(); i++) {
        vecs.emplace_back(B[(i + 1) % B.size()].first - B[i].first, B[(i + 1) % B.size()].second - B[i].second);
    }
    sort(vecs.begin(), vecs.end(), cmp);
    for (int i = 0; i < vecs.size(); i++) {
        if (i > 0 && tp(vecs[i]) == tp(vecs[i - 1]) && vecs[i].first * vecs[i - 1].second == vecs[i].second * vecs[i - 1].first) {
            fin.back().first += vecs[i].first;
            fin.back().second += vecs[i].second;
        }
        else {
            fin.emplace_back(fin.back().first + vecs[i].first, fin.back().second + vecs[i].second);
        }
    }
    assert(fin.back() == fin[0]);
    fin.pop_back();
    for (auto& it : fin) {
        it.first -= X;
        it.second -= Y;
    }
    ld ans = 0;
    const ld pi = acosl(-1.0);
    auto get_pt = [&](ll x1, ll y1) {
        ld D = sqrtl(x1 * x1 + y1 * y1);
        return make_pair(x1 * R / D, y1 * R / D);
    };
    auto get_ang = [&](pair<ld,ld>& P, pair<ld,ld>& Q) {
        ld T = (P.first * Q.first + P.second * Q.second);
        T /= sqrtl((P.first * P.first + P.second * P.second));
        T /= sqrtl((Q.first * Q.first + Q.second * Q.second));
        T = acosl(T);
        if (P.first * Q.second > P.second * Q.first) {
            return T * R * R / 2;
        }
        else {
            return (2 * pi - T) * R * R / 2;
        }
    };
    const ld eps = 1e-12;
    auto get = [&](ll x1, ll y1, ll x2, ll y2) {
        if (x1 * y2 == x2 * y1) return (ld)0.0;
        if (x1 * x1 + y1 * y1 > R * R) {
            swap(x1, x2);
            swap(y1, y2);
        }
        if (x1 * x1 + y1 * y1 <= R * R && x2 * x2 + y2 * y2 <= R * R) {
            return (ld)(llabs(x1 * y2 - x2 * y1)) / 2;
        }
        if (x1 * x1 + y1 * y1 >= R * R && x2 * x2 + y2 * y2 >= R * R) {
            if (x1 * y2 < x2 * y1) {
                swap(x1, x2);
                swap(y1, y2);
            }
            ll dx = x2 - x1;
            ll dy = y2 - y1;
            __int128 A = dx * dx + dy * dy;
            __int128 B = 2 * dx * x1 + 2 * dy * y1;
            __int128 C = x1 * x1 + y1 * y1 - R * R;
            __int128 D = B * B - 4 * A * C;
            auto P = get_pt(x1, y1);
            auto Q = get_pt(x2, y2);
            if (D <= 0) {
                return get_ang(P, Q);
            }
            ld t1 = (-B - sqrtl(D)) / (2 * A);
            ld t2 = (-B + sqrtl(D)) / (2 * A);
            if (t1 > -eps && t2 < 1 + eps) {
                pair<ld,ld> T1 = make_pair(x1 + dx * t1, y1 + dy * t1);
                pair<ld,ld> T2 = make_pair(x1 + dx * t2, y1 + dy * t2);
                return get_ang(P, T1) + get_ang(T2, Q) + (T1.first * T2.second - T2.first * T1.second) / 2;
            }
            else {
                return get_ang(P, Q);
            }
        }
        else {
            assert(x1 * x1 + y1 * y1 < R * R && x2 * x2 + y2 * y2 > R * R);

            ll dx = x2 - x1;
            ll dy = y2 - y1;
            __int128 A = dx * dx + dy * dy;
            __int128 B = 2 * dx * x1 + 2 * dy * y1;
            __int128 C = x1 * x1 + y1 * y1 - R * R;
            __int128 D = B * B - 4 * A * C;
            auto P = get_pt(x1, y1);
            auto Q = get_pt(x2, y2);
            assert(D > 0);
            ld t2 = (-B + sqrtl(D)) / (2 * A);
            assert(t2 > -eps && t2 < 1 + eps);
            pair<ld,ld> T2 = make_pair(x1 + dx * t2, y1 + dy * t2);
            if (x1 * y2 > x2 * y1) {
                return get_ang(T2, Q) + (x1 * T2.second - y1 * T2.first) / 2;
            }
            else {
                return get_ang(Q, T2) + (y1 * T2.first - x1 * T2.second) / 2;
            }
        }
    };
    for (int i = 0; i < fin.size(); i++) {
        ll x1 = fin[i].first;
        ll y1 = fin[i].second;
        ll x2 = fin[(i + 1) % fin.size()].first;
        ll y2 = fin[(i + 1) % fin.size()].second;
        if (x1 * y2 > x2 * y1) {
            ans += get(x1, y1, x2, y2);
        }
        else {
            ans -= get(x1, y1, x2, y2);
        }
    }
    cout << fixed << setprecision(4) << ans / (pi * R * R) << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 68ms
memory: 6812kb

input:

1122
11
-500 -114
-496 -490
-407 -500
462 -497
491 -243
492 -215
497 277
478 493
-415 498
-465 484
-495 176
15
-500 -11
-496 -403
-489 -497
-401 -499
-103 -499
447 -497
471 -476
477 -440
494 -290
488 367
482 451
454 489
3 499
-472 499
-497 469
713 -985 37
17
-496 17
-495 -430
-472 -492
-211 -500
76 ...

output:

0.6789
0.1050
0.0468
0.6318
0.7741
0.3651
0.7205
0.0861
0.5573
0.5395
0.6953
0.1941
0.9430
0.0230
0.8571
0.9358
0.1198
0.0000
0.0001
0.8291
0.8209
0.0002
0.3607
0.9495
0.0222
0.4078
0.7429
0.2767
0.0608
0.5269
0.3375
0.3681
0.3722
0.1868
0.7206
0.5713
0.9219
0.2378
0.6476
0.4897
0.6407
1.0000
0.5435...

result:

wrong answer 50th lines differ - expected: '0.0000', found: '-0.0000'