QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#454040 | #876. Big Brother | grass8cow# | WA | 227ms | 136780kb | C++17 | 1.9kb | 2024-06-24 16:01:03 | 2024-06-24 16:01:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define db long double
const db eps=1e-12;
int sgn(db a){
if(abs(a)<eps)return 0;
return a>0?1:-1;
}
db p2(db x){return x*x;}
struct no{
db x,y;
no(){x=0,y=0;}
no(db x_,db y_){x=x_,y=y_;}
no operator + (const no &a) const{return no(x+a.x,y+a.y);}
no operator - (const no &a) const{return no(x-a.x,y-a.y);}
no operator * (const db &k) const{return no(x*k,y*k);}
no operator / (const db &k) const{return no(x/k,y/k);}
inline db dis(no a){return p2(x-a.x)+p2(y-a.y);}
inline no rot(){return no(-y,x);}
};
db cro(no a,no b){return a.x*b.y-a.y*b.x;}
db sat(no a,no b,no c){return cro(b-a,c-a);}
struct ed{
no s,t;db jm;
ed(){}
ed(no s_,no t_){s=s_,t=t_,jm=atan2(t.y-s.y,t.x-s.x);}
inline int side(no a){return sgn(sat(s,t,a));}
bool operator < (const ed &a) const{
if(sgn(jm-a.jm)!=0)return jm<a.jm;
return sgn(sat(a.s,a.t,s))>0;
}
};
no jd(ed a,ed b){
db S1=sat(a.s,a.t,b.s),S2=sat(a.s,a.t,b.t);
return (b.t*S1-b.s*S2)/(S1-S2);
}
ed hf(no s,no t){
no m=s+t;m=m/2;
return ed(m,m+(t-s).rot());
}
bool ck(ed a,ed b,ed c){return a.side(jd(b,c))<0;}
int m,m_;
ed e[500010],e_[500010],q[500010];
int l,r;
void gethalf(){
sort(e+1,e+m+1);
m_=0;
for(int i=1;i<=m;i++){
if(m_&&!sgn(e_[m_].jm-e[i].jm))continue;
e_[++m_]=e[i];
}
m=m_;for(int i=1;i<=m;i++)e[i]=e_[i];
l=1,r=0;
for(int i=1;i<=m;i++){
while(l<r&&ck(e[i],q[r],q[r-1]))r--;
q[++r]=e[i];
}
while(l<r&&ck(q[l],q[r-1],q[r]))r--;
while(l<r&&ck(q[l+1],q[l],q[r]))l++;
}
no a[500010];
int main(){
int n;scanf("%d",&n);
db x,y;
for(int i=1;i<=n;i++)scanf("%Lf%Lf",&x,&y),a[i]=no(x,y);
for(int i=n;i;i--)e[++m]=ed(a[i%n+1],a[i]);
gethalf();
n=0;
for(int i=l;i<r;i++)a[++n]=jd(q[i],q[i+1]);
if(r-l>1)a[++n]=jd(q[r],q[l]);
db ans=0;
for(int i=1;i<=n;i++)ans+=cro(a[i],a[i%n+1]);
return printf("%.10Lf",abs(ans)/2),0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 34ms
memory: 136732kb
input:
8 0 0 0 1 1 1 1 2 2 2 2 1 3 1 3 0
output:
1.0000000000
result:
ok "1.000000000"
Test #2:
score: 0
Accepted
time: 27ms
memory: 136764kb
input:
8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0
output:
0.0000000000
result:
ok "0.000000000"
Test #3:
score: 0
Accepted
time: 11ms
memory: 136656kb
input:
6 140 62 97 141 68 156 129 145 153 176 130 109
output:
48.8034950021
result:
ok "48.803495002"
Test #4:
score: 0
Accepted
time: 13ms
memory: 136696kb
input:
3 198 165 322 122 242 84
output:
4076.0000000000
result:
ok "4076.000000000"
Test #5:
score: 0
Accepted
time: 15ms
memory: 136684kb
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.0000000000
result:
ok "62500.000000000"
Test #6:
score: 0
Accepted
time: 31ms
memory: 136680kb
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.3646559959
result:
ok "114711.364655996"
Test #7:
score: 0
Accepted
time: 21ms
memory: 136780kb
input:
6 160 210 200 210 200 300 280 300 200 170 200 80
output:
0.0000000000
result:
ok "0.000000000"
Test #8:
score: 0
Accepted
time: 23ms
memory: 136660kb
input:
8 198 165 230 113 246 117 281 161 266 36 247 68 228 79 200 30
output:
63.7023612504
result:
ok "63.702361250"
Test #9:
score: 0
Accepted
time: 19ms
memory: 136732kb
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.0016479133
result:
ok "2189.001647913"
Test #10:
score: 0
Accepted
time: 8ms
memory: 136656kb
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.1393890381
result:
ok "77922149990018.218750000"
Test #11:
score: 0
Accepted
time: 19ms
memory: 136700kb
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.9890060425
result:
ok "78537708558542.031250000"
Test #12:
score: 0
Accepted
time: 24ms
memory: 136764kb
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.7439498901
result:
ok "78539327974559.937500000"
Test #13:
score: 0
Accepted
time: 118ms
memory: 136696kb
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.2608108521
result:
ok "78525334096415.250000000"
Test #14:
score: 0
Accepted
time: 227ms
memory: 136724kb
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.8614501953
result:
ok "78479009888752.796875000"
Test #15:
score: 0
Accepted
time: 7ms
memory: 136596kb
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.5501461029
result:
ok "11331974361764.560546875"
Test #16:
score: 0
Accepted
time: 28ms
memory: 136704kb
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.1469821930
result:
ok "302585512646.140625000"
Test #17:
score: -100
Wrong Answer
time: 30ms
memory: 136764kb
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:
121147140.8621826172
result:
wrong answer 1st numbers differ: expected 121175133.1328125000, found 121147140.8621826172, absolute error = 27992.2706298828, error = 0.000231