QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#166034#6850. Amazing spacecraftPPPAC ✓43ms7072kbC++176.1kb2023-09-06 00:13:302023-09-06 00:13:30

Judging History

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

  • [2023-09-06 00:13:30]
  • 评测
  • 测评结果:AC
  • 用时:43ms
  • 内存:7072kb
  • [2023-09-06 00:13:30]
  • 提交

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;
    }
//    R = 5;
//    fin = {{3, 4}, {3, 12}, {-3, 12}, {-3, 4}};
    pair<ll,ll> zero = {0, 0};
    bool has_int = false;

    vector<pair<pair<ld,ld>,pair<int,pair<int,ld>>>> CC;
    const int LINE = 0;
    const int CIRCLE = 1;
    const ld eps = 1e-6;
    bool has_inside = false;
    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 * x1 + y1 * y1 <= R * R) {
            CC.emplace_back(make_pair(x1, y1), make_pair(LINE, make_pair(i, 0)));
            has_inside = true;
        }
        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;
        if (D < 0) continue;
        if (-B > 0 && C > 0) {
            if ((-B - 2 * A) <= 0 || (D >= (B + 2 * A) * (B + 2 * A))) {
                ld t = (-B - sqrtl(D)) / (2 * A);
                assert(t > -eps && t < 1 + eps);
                CC.emplace_back(make_pair(x1 + dx * t, y1 + dy * t), make_pair(CIRCLE, make_pair(i, t)));
                has_int |= (D > 0);
            }
        }
        if (B <= 0 || D >= B * B) {
            if (2 * A + B > 0 && (2 * A + B) * (2 * A + B) > D) {
                ld t = (-B + sqrtl(D)) / (2 * A);
                CC.emplace_back(make_pair(x1 + dx * t, y1 + dy * t), make_pair(CIRCLE, make_pair(i, t)));
                assert(t > -eps && t < 1 + eps);
                has_int |= (D > 0);
            }
        }
    }
//    for (int i = 0; i < CC.size(); i++) {
//        if (CC[i].second.first == CIRCLE) has_int = true;
//        if ((i + 1) > 0)
//        cout << CC[i].first.first << " " << CC[i].first.second << " " << CC[i].second.first << " " << CC[i].second.second << endl;
//    }
    const ld pi = acosl(-1.0);
    if (!has_int) {
        ll S = 0;
        for (int i = 1; i + 1 < fin.size(); i++) {
            S += area(fin[0], fin[i], fin[i + 1]);
        }
        ll my_ar = 0;
        for (int i = 0; i < fin.size(); i++) {
            my_ar += llabs(area(zero, fin[i], fin[(i + 1) % fin.size()]));
        }
        if (has_inside) {
            cout << fixed << setprecision(4) << (ld)llabs(S) / (2 * pi * R * R) << '\n';
        }
        else {
            if (my_ar == S) {
                cout << fixed << setprecision(4) << 1.0 << '\n';
            }
            else {
                cout << fixed << setprecision(4) << 0.0 << '\n';
            }
        }
        return;
    }
    ld ans = 0;
    const ld eps2 = 1e-12;
    for (int i = 0; i < CC.size(); i++) {
        auto t1 = CC[i];
        auto t2 = CC[(i + 1) % CC.size()];
        if (t1.second.first == CIRCLE && t2.second.first == CIRCLE &&
            (t1.second.second.first != t2.second.second.first || t1.second.second.second > t2.second.second.second)) {
            //circle
            ld ang1 = atan2(t1.first.second, t1.first.first);
            ld ang2 = atan2(t2.first.second, t2.first.first);
            if (fabsl(t1.second.second.second - t2.second.second.second) < eps2) {
                continue;
            }
            ang2 -= ang1;
            if (ang2 < 0) ang2 += 2 * pi;
            ans += ang2 * R * R / 2;
        }
        else {
            ld s = t2.first.second  * t1.first.first - t1.first.second * t2.first.first;
            ans += s / 2;
        }
    }
    if ((ans / (pi * R * R)) < eps) {
        cout << "0.0000\n";
        return;
    }
    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 43ms
memory: 7072kb

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:

ok 1122 lines