QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243919 | #876. Big Brother | JooDdae | WA | 849ms | 50048kb | C++20 | 2.6kb | 2023-11-08 19:16:42 | 2023-11-08 19:16:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using point = array<ld, 2>;
using line = array<point, 2>;
static const ld eps = 1e-13;
ld solve(const vector<point> &p){
auto plus = [&](point p, point q)->point{
return {p[0] + q[0], p[1] + q[1]};
};
auto minus = [&](point p, point q)->point{
return {p[0] - q[0], p[1] - q[1]};
};
auto dot = [&](point p, point q)->ld{
return p[0] * q[0] + p[1] * q[1];
};
auto mul = [&](ld c, point p)->point{
return {p[0] * c, p[1] * c};
};
auto cross = [&](point p, point q)->ld{
return p[0] * q[1] - p[1] * q[0];
};
auto inter = [&](line s, line t)->point{
ld alpha = cross(minus(t[0], s[0]), t[1]) / cross(s[1], t[1]);
return plus(s[0], mul(alpha, s[1]));
};
int n = p.size();
vector<line> hps(n);
for(int i=0;i<n;i++) hps[i] = {p[(i+1)%n], minus(p[i], p[(i+1)%n])};
sort(hps.begin(), hps.end(), [&](line a, line b) {
ld aang = atan2l(a[1][1], a[1][0]), bang = atan2l(b[1][1], b[1][0]);
if(aang != bang) return aang < bang;
line c = line({point({0, 0}), point({a[1][1], a[1][0]})});
ld cang = atan2l(c[1][1], c[1][0]);
point A = inter(c, a), B = inter(c, b);
point C = b[0];
C[0] -= b[1][0] * 14124412;
C[1] -= b[1][1] * 14124412;
return cross(minus(B, C), minus(A, C)) > 0;
});
auto bad = [&](line l, line m, line n)->bool{
auto s = cross(l[1], m[1]);
if(abs(s) < eps) return false;
auto p = cross(n[1], minus(plus(mul(s, l[0]), mul(cross(minus(m[0], l[0]), m[1]), l[1])), mul(s, n[0])));
return s > 0 ? p <= eps : p >= -eps;
};
deque<line> dq;
for(auto p: hps){
if(!dq.empty() && abs(cross(dq.back()[1], p[1])) <= eps) continue;
while((int)dq.size() >= 2 && bad(dq[(int)dq.size() - 2], dq.back(), p)) dq.pop_back();
while((int)dq.size() >= 2 && bad(dq[0], dq[1], p)) dq.pop_front();
if((int)dq.size() < 2 || !bad(dq.back(), p, dq.front())) dq.push_back(p);
}
if(dq.size() < 3) return 0;
int N = dq.size();
vector<point> np(N);
for(int i=0;i<N;i++) np[i] = inter(dq[i], dq[(i+1)%N]);
ld re = 0;
for(int i=0;i<N;i++) re += cross(np[i], np[(i+1)%N]);
return abs(re)/2;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(15);
int n; cin >> n;
vector<point> p(n);
for(auto &[x, y] : p) cin >> x >> y;
cout << solve(p);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
8 0 0 0 1 1 1 1 2 2 2 2 1 3 1 3 0
output:
1.000000000000000
result:
ok "1.000000000"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0
output:
0.000000000000000
result:
ok "0.000000000"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
6 140 62 97 141 68 156 129 145 153 176 130 109
output:
48.803495002058103
result:
ok "48.803495002"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
3 198 165 322 122 242 84
output:
4076.000000000000000
result:
ok "4076.000000000"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3792kb
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.000000000000000
result:
ok "62500.000000000"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3652kb
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.364655995883794
result:
ok "114711.364655996"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
6 160 210 200 210 200 300 280 300 200 170 200 80
output:
0.000000000000000
result:
ok "0.000000000"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
8 198 165 230 113 246 117 281 161 266 36 247 68 228 79 200 30
output:
63.702361250448232
result:
ok "63.702361250"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3628kb
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.001647913251940
result:
ok "2189.001647913"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3660kb
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.139389038085938
result:
ok "77922149990018.218750000"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3860kb
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:
78537708558541.989006042480469
result:
ok "78537708558542.031250000"
Test #12:
score: 0
Accepted
time: 69ms
memory: 8320kb
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:
78539328042311.010902404785156
result:
ok "78539327974559.937500000"
Test #13:
score: 0
Accepted
time: 411ms
memory: 26960kb
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:
78525346698716.009788513183594
result:
ok "78525334096415.250000000"
Test #14:
score: -100
Wrong Answer
time: 849ms
memory: 50048kb
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:
78479129735991.933929443359375
result:
wrong answer 1st numbers differ: expected 78479009888752.7968750000, found 78479129735991.9375000000, absolute error = 119847239.1406250000, error = 0.000002