QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#165909 | #6850. Amazing spacecraft | PPP# | WA | 34ms | 7012kb | C++17 | 6.0kb | 2023-09-05 22:54:50 | 2023-09-05 22:54:50 |
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 = 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;
}
}
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: 34ms
memory: 7012kb
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'