QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#166026 | #6850. Amazing spacecraft | PPP | AC ✓ | 78ms | 11744kb | C++17 | 6.0kb | 2023-09-06 00:11:00 | 2023-09-06 00:11:00 |
Judging History
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 = 2e5 + 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);
}
void solve() {
cin >> n;
vector<pair<ll,ll>> A, B;
set<pair<ll,ll>> AA;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
x[i] *= -1;
y[i] *= -1;
if (AA.count({x[i], y[i]})) continue;
AA.insert({x[i], y[i]});
A.emplace_back(x[i], y[i]);
}
cin >> m;
AA.clear();
for (int i = 1; i <= m; i++) {
cin >> px[i] >> py[i];
if (AA.count({px[i], py[i]})) continue;
AA.insert({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);
assert(T1.first * T2.second + eps > T2.first * T1.second);
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);
}
}
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: 78ms
memory: 11744kb
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