QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#166031#6850. Amazing spacecraftPPPWA 43ms6996kbC++176.1kb2023-09-06 00:12:342023-09-06 00:12:35

Judging History

This is the latest submission verdict.

  • [2023-09-06 00:12:35]
  • Judged
  • Verdict: WA
  • Time: 43ms
  • Memory: 6996kb
  • [2023-09-06 00:12:34]
  • 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;
    }
//    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 << '\n';
            }
            else {
                cout << fixed << setprecision(4) << 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;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 43ms
memory: 6996kb

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
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
0.5435
0.8389
0....

result:

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