QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709627 | #876. Big Brother | becaido | AC ✓ | 170ms | 42880kb | C++20 | 3.7kb | 2024-11-04 15:57:12 | 2024-11-04 15:57:15 |
Judging History
answer
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << "\n";}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 5e5 + 5;
int n;
struct point {
ll x = 0, y = 0;
point() {}
point(ll x, ll y) : x(x), y(y) {}
point operator - (const point &o) const {
return point(x - o.x, y - o.y);
}
ll operator * (const point &o) const {
return x * o.y - y * o.x;
}
ll abs2() {
return x * x + y * y;
}
void get() {
cin >> x >> y;
}
} p[SIZE];
struct Line {
point X, Y;
Line() {}
Line(point X, point Y) : X(X), Y(Y) {}
};
int sign(ll x) {
return x > 0 ? 1 : x < 0 ? -1 : 0;
}
int ori(point a, point b, point c) {
return sign((b - a) * (c - a));
}
int cmp(point a, point b, bool same = true) {
#define is_neg(k) (sign(k.y) < 0 || (sign(k.y) == 0 && sign(k.x) < 0))
int A = is_neg(a), B = is_neg(b);
if (A != B) return A < B;
if (sign(a * b) == 0) return same ? a.abs2() < b.abs2() : -1;
return sign(a * b) > 0;
}
pair<ll, ll> area_pair(Line a, Line b) {
return pair<ll, ll>((a.Y - a.X) * (b.X - a.X), (a.Y - a.X) * (b.Y - a.X));
}
bool isin(Line l0, Line l1, Line l2) {
auto [a02X, a02Y] = area_pair(l0, l2);
auto [a12X, a12Y] = area_pair(l1, l2);
if (a12X - a12Y < 0) a12X *= -1, a12Y *= -1;
return (__int128) a02Y * a12X - (__int128) a02X * a12Y > 0;
}
vector<Line> halfPlaneInter(vector<Line> arr) {
sort(arr.begin(), arr.end(), [&](Line a, Line b) ->int {
if (cmp(a.Y - a.X, b.Y - b.X, 0) != -1) return cmp(a.Y - a.X, b.Y - b.X, 0);
return ori(a.X, a.Y, b.Y) < 0;
});
deque<Line> dq(1, arr[0]);
auto pop_back = [&](int t, Line p) {
while (dq.size() >= t && !isin(p, dq[dq.size() - 2], dq.back())) dq.pop_back();
};
auto pop_front = [&](int t, Line p) {
while (dq.size() >= t && !isin(p, dq[0], dq[1])) dq.pop_front();
};
for (auto p : arr) {
if (cmp(dq.back().Y - dq.back().X, p.Y - p.X, 0) != -1) {
pop_back(2, p);
pop_front(2, p);
dq.pb(p);
}
}
pop_back(3, dq[0]), pop_front(3, dq.back());
return vector<Line>(dq.begin(), dq.end());
}
pair<double, double> ints(point p1, point p2, point p3, point p4) {
double a123 = (p2 - p1) * (p3 - p1);
double a124 = (p2 - p1) * (p4 - p1);
double x = (p4.x * a123 - p3.x * a124) / (a123 - a124);
double y = (p4.y * a123 - p3.y * a124) / (a123 - a124);
return {x, y};
}
void solve() {
cin >> n;
FOR (i, 1, n) p[i].get();
reverse(p + 1, p + n + 1);
vector<Line> v;
FOR (i, 1, n - 1) v.pb(Line(p[i], p[i + 1]));
v.pb(Line(p[n], p[1]));
v = halfPlaneInter(v);
if (v.size() <= 2) {
cout << "0.00\n";
return;
}
vector<pair<double, double>> ans;
FOR (i, 0, v.size() - 2) ans.pb(ints(v[i].X, v[i].Y, v[i + 1].X, v[i + 1].Y));
ans.pb(ints(v.back().X, v.back().Y, v[0].X, v[0].Y));
double area = 0;
ans.pb(ans[0]);
FOR (i, 0, ans.size() - 2) {
auto [x, y] = ans[i];
auto [nx, ny] = ans[i + 1];
area += x * ny - y * nx;
}
cout << fixed << setprecision(12) << abs(area / 2) << '\n';
}
int main() {
Waimai;
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11692kb
input:
8 0 0 0 1 1 1 1 2 2 2 2 1 3 1 3 0
output:
1.000000000000
result:
ok "1.000000000"
Test #2:
score: 0
Accepted
time: 2ms
memory: 11612kb
input:
8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0
output:
0.00
result:
ok "0.000000000"
Test #3:
score: 0
Accepted
time: 3ms
memory: 11676kb
input:
6 140 62 97 141 68 156 129 145 153 176 130 109
output:
48.803495002059
result:
ok "48.803495002"
Test #4:
score: 0
Accepted
time: 0ms
memory: 11704kb
input:
3 198 165 322 122 242 84
output:
4076.000000000000
result:
ok "4076.000000000"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11628kb
input:
15 0 250 30 250 125 250 180 250 250 250 250 100 250 80 250 0 140 0 100 0 73 0 0 0 0 2 0 30 0 90
output:
62500.000000000000
result:
ok "62500.000000000"
Test #6:
score: 0
Accepted
time: 0ms
memory: 11548kb
input:
16 146 145 109 229 139 301 164 385 221 433 309 419 405 420 447 369 501 308 498 229 471 150 456 75 391 39 308 47 227 39 166 73
output:
114711.364655995887
result:
ok "114711.364655996"
Test #7:
score: 0
Accepted
time: 2ms
memory: 11356kb
input:
6 160 210 200 210 200 300 280 300 200 170 200 80
output:
0.00
result:
ok "0.000000000"
Test #8:
score: 0
Accepted
time: 2ms
memory: 11848kb
input:
8 198 165 230 113 246 117 281 161 266 36 247 68 228 79 200 30
output:
63.702361250449
result:
ok "63.702361250"
Test #9:
score: 0
Accepted
time: 2ms
memory: 11708kb
input:
14 198 165 274 226 258 318 297 348 339 309 372 360 336 265 347 203 388 161 346 123 306 155 293 87 261 112 242 84
output:
2189.001647913257
result:
ok "2189.001647913"
Test #10:
score: 0
Accepted
time: 2ms
memory: 11656kb
input:
150 9956003 4338159 9912302 4099714 9868603 3861269 9803272 3631902 9737943 3402535 9725452 3366405 9712963 3330276 9696862 3286153 9680763 3242031 9604920 3061837 9529080 2881643 9480997 2784399 9432916 2687155 9193856 2313907 8954799 1940659 8617533 1583544 8280269 1226429 8207226 1165339 8134185 ...
output:
77922149990018.109375000000
result:
ok "77922149990018.218750000"
Test #11:
score: 0
Accepted
time: 0ms
memory: 11752kb
input:
1000 9999605 4937170 9999012 4905760 9998421 4874350 9997433 4842949 9996447 4811549 9995065 4780163 9993685 4748778 9991908 4717412 9990134 4686047 9987963 4654706 9985795 4623366 9983230 4592055 9980668 4560744 9977710 4529467 9974755 4498191 9971405 4466954 9968057 4435718 9964314 4404526 9960574...
output:
78537708558542.000000000000
result:
ok "78537708558542.031250000"
Test #12:
score: 0
Accepted
time: 14ms
memory: 14448kb
input:
50000 10000000 4998743 9999998 4998115 9999999 4997487 9999998 4996858 9999999 4996230 9999997 4995601 9999997 4994973 9999995 4994345 9999996 4993717 9999994 4993088 9999994 4992460 9999992 4991832 9999992 4991204 9999990 4990575 9999990 4989947 9999987 4989318 9999987 4988690 9999984 4988062 99999...
output:
78539327974559.718750000000
result:
ok "78539327974559.937500000"
Test #13:
score: 0
Accepted
time: 59ms
memory: 26736kb
input:
250000 10000000 4999749 9999999 4999623 10000000 4999497 9999999 4999371 10000000 4999246 9999999 4999120 10000000 4998995 9999999 4998869 10000000 4998743 9999999 4998617 10000000 4998492 9999999 4998366 10000000 4998241 9999999 4998115 10000000 4997989 9999998 4997863 9999999 4997738 9999998 49976...
output:
78525334096415.359375000000
result:
ok "78525334096415.250000000"
Test #14:
score: 0
Accepted
time: 146ms
memory: 42480kb
input:
500000 10000000 4999874 9999999 4999811 10000000 4999749 9999999 4999686 10000000 4999623 9999999 4999560 10000000 4999497 9999999 4999434 10000000 4999372 9999999 4999309 10000000 4999246 9999999 4999183 10000000 4999120 9999999 4999057 10000000 4998995 9999999 4998932 10000000 4998869 9999999 4998...
output:
78479009888752.734375000000
result:
ok "78479009888752.796875000"
Test #15:
score: 0
Accepted
time: 3ms
memory: 11624kb
input:
150 9725000 5000000 9496052 4811560 9932639 4585795 9464516 4436001 9658831 4212018 9401664 4064398 9794486 3768986 9307937 3699357 9462178 3446106 9183994 3343440 9522050 2986654 9030702 2999142 9140549 2723714 8849139 2668879 9122960 2260712 8640576 2354967 8702951 2065077 8406477 2059608 8608394 ...
output:
11331974361764.552734375000
result:
ok "11331974361764.560546875"
Test #16:
score: 0
Accepted
time: 2ms
memory: 11800kb
input:
1000 9725000 5000000 9499911 4971726 9949609 4937799 9499200 4915183 9723507 4881261 9497779 4858652 9946482 4813434 9495648 4802144 9719032 4762596 9492806 4745667 9940232 4689187 9489256 4689230 9711575 4644081 9484996 4632843 9930861 4565137 9480028 4576513 9701143 4525791 9474353 4520250 9918375...
output:
302585512646.136718750000
result:
ok "302585512646.140625000"
Test #17:
score: 0
Accepted
time: 16ms
memory: 14052kb
input:
50000 9725000 5000000 9499999 4999435 9949999 4998756 9499999 4998304 9724999 4997625 9499999 4997173 9949998 4996268 9499998 4996042 9724997 4995250 9499997 4994911 9949996 4993780 9499995 4993780 9724994 4992875 9499993 4992649 9949992 4991292 9499992 4991518 9724990 4990500 9499989 4990387 994998...
output:
121175133.183593750000
result:
ok "121175133.132812500"
Test #18:
score: 0
Accepted
time: 68ms
memory: 26864kb
input:
250000 9725000 5000000 9499999 4999887 9949999 4999752 9499999 4999661 9724999 4999525 9499999 4999435 9949999 4999254 9499999 4999209 9724999 4999050 9499999 4998983 9949999 4998756 9499999 4998756 9724999 4998575 9499999 4998530 9949999 4998259 9499999 4998304 9724999 4998100 9499999 4998078 99499...
output:
4772368.080078125000
result:
ok "4772368.076171875"
Test #19:
score: 0
Accepted
time: 152ms
memory: 42768kb
input:
500000 9725000 5000000 9499999 4999944 9949999 4999876 9499999 4999831 9724999 4999763 9499999 4999718 9949999 4999627 9499999 4999605 9724999 4999525 9499999 4999492 9949999 4999378 9499999 4999378 9724999 4999288 9499999 4999265 9949999 4999130 9499999 4999152 9724999 4999050 9499999 4999039 99499...
output:
1169025.591796875000
result:
ok "1169025.593750000"
Test #20:
score: 0
Accepted
time: 3ms
memory: 11616kb
input:
72 4 50 4 51 5 56 6 60 7 63 9 68 10 70 13 75 15 78 18 82 19 83 23 86 26 88 31 91 33 92 38 94 41 95 45 96 50 97 51 97 56 96 60 95 63 94 68 92 70 91 75 88 78 86 82 83 83 82 86 78 88 75 91 70 92 68 94 63 95 60 96 56 97 51 97 50 96 45 95 41 94 38 92 33 91 31 88 26 86 23 83 19 82 18 78 15 75 13 70 10 68 ...
output:
6435.000000000000
result:
ok "6435.000000000"
Test #21:
score: 0
Accepted
time: 0ms
memory: 11560kb
input:
72 4 50 4 51 5 56 6 60 7 63 9 68 10 70 13 75 15 78 18 82 20 82 23 86 26 88 31 91 33 92 38 94 41 95 45 96 50 97 51 97 56 96 60 95 63 94 68 92 70 91 75 88 78 86 82 83 83 82 86 78 88 75 91 70 91 68 94 63 95 60 96 56 97 51 97 50 96 45 95 41 94 38 92 33 91 31 88 26 86 23 83 19 82 18 78 15 75 13 70 10 68 ...
output:
4180.100000000001
result:
ok "4180.100000000"
Test #22:
score: 0
Accepted
time: 0ms
memory: 11748kb
input:
336 10 500 10 501 11 512 12 522 13 531 14 539 15 546 16 552 18 563 19 568 21 577 22 581 25 592 27 599 30 609 31 612 35 623 38 631 40 636 43 643 47 652 52 663 53 665 59 676 64 685 68 692 71 697 76 705 83 716 85 719 92 729 97 736 105 747 108 751 115 760 119 765 128 776 133 782 139 789 146 797 154 806 ...
output:
708179.000000000000
result:
ok "708179.000000000"
Test #23:
score: 0
Accepted
time: 2ms
memory: 11816kb
input:
336 10 500 10 501 11 512 12 522 13 531 14 539 15 546 16 552 18 563 19 568 21 577 22 581 25 592 27 599 30 609 31 612 35 623 38 631 40 636 43 643 47 652 52 663 53 665 59 676 64 685 68 692 71 697 76 705 83 716 85 719 92 729 97 736 105 747 109 750 115 760 119 765 128 776 133 782 139 789 146 797 154 806 ...
output:
696280.075865801075
result:
ok "696280.075865801"
Test #24:
score: 0
Accepted
time: 0ms
memory: 11840kb
input:
1576 22 5000 22 5001 23 5026 24 5050 25 5073 26 5095 27 5116 28 5136 29 5155 30 5173 31 5190 32 5206 33 5221 34 5235 35 5248 37 5273 38 5285 40 5308 41 5319 43 5340 44 5350 46 5369 47 5378 49 5395 52 5420 53 5428 56 5451 58 5466 61 5488 62 5495 65 5515 67 5528 70 5547 74 5572 75 5578 79 5601 82 5618...
output:
73741747.000000000000
result:
ok "73741747.000000000"
Test #25:
score: 0
Accepted
time: 2ms
memory: 11820kb
input:
1576 22 5000 22 5001 23 5026 24 5050 25 5073 26 5095 27 5116 28 5136 29 5155 30 5173 31 5190 32 5206 33 5221 34 5235 35 5248 37 5273 38 5285 40 5308 41 5319 43 5340 44 5350 46 5369 47 5378 49 5395 52 5420 53 5428 56 5451 58 5466 61 5488 62 5495 65 5515 67 5528 70 5547 74 5572 75 5578 79 5601 82 5618...
output:
73705049.076299577951
result:
ok "73705049.076299563"
Test #26:
score: 0
Accepted
time: 4ms
memory: 11960kb
input:
7328 7 50000 7 50001 8 50056 9 50110 10 50163 11 50215 12 50266 13 50316 14 50365 15 50413 16 50460 17 50506 18 50551 19 50595 20 50638 21 50680 22 50721 23 50761 24 50800 25 50838 26 50875 27 50911 28 50946 29 50980 30 51013 31 51045 32 51076 33 51106 34 51135 35 51163 37 51218 38 51245 40 51298 41...
output:
7448951491.000000000000
result:
ok "7448951491.000000000"
Test #27:
score: 0
Accepted
time: 2ms
memory: 12016kb
input:
7328 7 50000 7 50001 8 50056 9 50110 10 50163 11 50215 12 50266 13 50316 14 50365 15 50413 16 50460 17 50506 18 50551 19 50595 20 50638 21 50680 22 50721 23 50761 24 50800 25 50838 26 50875 27 50911 28 50946 29 50980 30 51013 31 51045 32 51076 33 51106 34 51135 35 51163 37 51218 38 51245 40 51298 41...
output:
7448332528.534090995789
result:
ok "7448332528.534090042"
Test #28:
score: 0
Accepted
time: 11ms
memory: 15172kb
input:
33920 55 500000 55 500001 56 500119 57 500236 58 500352 59 500467 60 500581 61 500694 62 500806 63 500917 64 501027 65 501136 66 501244 67 501351 68 501457 69 501562 70 501666 71 501769 72 501871 73 501972 74 502072 75 502171 76 502269 77 502366 78 502462 79 502557 80 502651 81 502744 82 502836 83 5...
output:
741575176515.000000000000
result:
ok "741575176515.000000000"
Test #29:
score: 0
Accepted
time: 7ms
memory: 15104kb
input:
33920 55 500000 55 500001 56 500119 57 500236 58 500352 59 500467 60 500581 61 500694 62 500806 63 500917 64 501027 65 501136 66 501244 67 501351 68 501457 69 501562 70 501666 71 501769 72 501871 73 501972 74 502072 75 502171 76 502269 77 502366 78 502462 79 502557 80 502651 81 502744 82 502836 83 5...
output:
741573412548.757446289062
result:
ok "741573412548.757324219"
Test #30:
score: 0
Accepted
time: 35ms
memory: 31008kb
input:
157336 187 5000000 187 5000001 188 5000256 189 5000510 190 5000763 191 5001015 192 5001266 193 5001516 194 5001765 195 5002013 196 5002260 197 5002506 198 5002751 199 5002995 200 5003238 201 5003480 202 5003721 203 5003961 204 5004200 205 5004438 206 5004675 207 5004911 208 5005146 209 5005380 210 5...
output:
74106620545235.000000000000
result:
ok "74106620545235.000000000"
Test #31:
score: 0
Accepted
time: 38ms
memory: 32380kb
input:
157336 187 5000000 187 5000001 188 5000256 189 5000510 190 5000763 191 5001015 192 5001266 193 5001516 194 5001765 195 5002013 196 5002260 197 5002506 198 5002751 199 5002995 200 5003238 201 5003480 202 5003721 203 5003961 204 5004200 205 5004438 206 5004675 207 5004911 208 5005146 209 5005380 210 5...
output:
74103087971323.859375000000
result:
ok "74103087971323.890625000"
Test #32:
score: 0
Accepted
time: 3ms
memory: 11460kb
input:
1000 2600927 1831555 2984114 2324333 2787576 1961497 2689538 1755826 3028761 2094323 3008306 1946570 2887360 1607548 2631170 1248827 2470347 1030200 2599775 976740 2355502 478504 3115957 1757729 3013991 1652055 3820728 3275946 3463130 2975465 2475784 1734142 1806440 809618 1228787 158466 889070 1047...
output:
0.00
result:
ok "0.000000000"
Test #33:
score: 0
Accepted
time: 3ms
memory: 11640kb
input:
100 3929758 5668516 3749933 7186400 3671700 7927629 3735926 8648648 3696539 9488835 4063262 5499567 4098011 5704292 4139678 6088717 4070777 5280029 4228917 6549215 4520598 8419214 4828480 8246428 4211962 5750987 4483103 6401689 4610886 6564084 5813897 9050031 5230681 7607146 6109094 7997896 5521186 ...
output:
4397951.337890625000
result:
ok "4397951.332031250"
Test #34:
score: 0
Accepted
time: 2ms
memory: 11644kb
input:
339 9841560 4381918 5523440 4169860 9115892 4287496 8727198 4244767 5647505 4166184 6094829 4167703 8084370 4141154 8447161 4040556 7127522 4080692 9371627 3948065 8433750 3853008 8813865 3806327 5596744 4123253 9468765 3650496 8552072 3729494 7603308 3772657 9093114 3424080 6269139 3962293 5674235 ...
output:
32849.080078125000
result:
ok "32849.078125000"
Test #35:
score: 0
Accepted
time: 3ms
memory: 11836kb
input:
4063 499799 2678043 2533563 4266964 403464 2618451 1221250 3278868 105760 2429242 226632 2525041 215412 2517220 64334 2404256 2592208 4345606 811663 3027094 4044746 5463601 1404325 3485231 1786865 3771953 1076645 3252401 99034 2529000 3694400 5206336 2511697 4333861 73213 2556268 2066557 4031607 138...
output:
232.302734375000
result:
ok "232.306640625"
Test #36:
score: 0
Accepted
time: 8ms
memory: 12188kb
input:
20000 8066872 8602921 8232035 8787201 5776793 6015019 5878121 6129006 5025917 5167705 8660957 9266687 8658850 9263857 5327441 5507461 6546784 6882138 9179876 9850214 6853075 7226685 8949733 9588511 6930959 7311116 7507630 7960229 6399255 6711831 9080160 9728973 7405711 7844429 6878616 7249568 747610...
output:
0.074218750000
result:
ok "0.074218750"
Test #37:
score: 0
Accepted
time: 170ms
memory: 42880kb
input:
500000 953759 7297457 2580377 6153306 2634043 6115587 2839957 5970786 486723 7626180 2227022 6402004 1225883 7106390 139747 7870702 404456 7684670 1928896 6612075 549400 7583058 1773913 6721479 425016 7670854 2329665 6330471 465562 7642533 375055 7706403 601385 7547144 198343 7830881 359197 7717867 ...
output:
0.001953125000
result:
ok "0.000000000"
Test #38:
score: 0
Accepted
time: 3ms
memory: 11804kb
input:
1000 1775807 6865631 4871886 8023283 7398086 8967646 143850 6312725 50868 6279999 4241424 7822696 22120 6286274 1098695 6682176 2064750 7034586 1875528 6981944 2387779 7184399 4969521 8131866 3585627 7642928 1961372 7069219 4352603 7948808 6407440 8673598 1789021 7127821 2036724 7247311 2738127 7483...
output:
5130.835937500000
result:
ok "5130.828125000"
Test #39:
score: 0
Accepted
time: 3ms
memory: 11800kb
input:
997 6923752 3142103 6035265 1166112 7134771 3679045 6503138 2357309 5554003 296869 6328294 2053182 5780625 885548 7317116 4249183 7819975 5401363 5642829 856378 7197673 4155115 7364650 4528812 6776562 3318236 5364427 497625 8844837 7590432 6698006 3244990 7640716 5174617 8857860 7626107 6979782 3911...
output:
5131.835937500000
result:
ok "5131.828125000"
Test #40:
score: 0
Accepted
time: 0ms
memory: 11808kb
input:
1000 9150738 1660620 8900040 3385771 9165624 1099746 9250879 361608 9026045 2195006 9016856 2243604 8908088 3047880 8641345 5262477 8796554 3843222 8898993 2719422 9033383 1282868 9110500 514669 8853009 2956351 9100138 459660 8690975 4209259 9048387 560131 8975462 1191225 8601171 5002153 8675233 419...
output:
29111.765625000000
result:
ok "29111.765625000"