QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#454040#876. Big Brothergrass8cow#WA 227ms136780kbC++171.9kb2024-06-24 16:01:032024-06-24 16:01:03

Judging History

你现在查看的是最新测评结果

  • [2024-06-24 16:01:03]
  • 评测
  • 测评结果:WA
  • 用时:227ms
  • 内存:136780kb
  • [2024-06-24 16:01:03]
  • 提交

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