QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#34436#876. Big BrotherFroggyguaRE 248ms58128kbC++175.8kb2022-06-09 08:05:002022-06-09 08:05:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-09 08:05:01]
  • 评测
  • 测评结果:RE
  • 用时:248ms
  • 内存:58128kb
  • [2022-06-09 08:05:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
const double PI=acos(-1.0);
const double inf=1e9+233;
//Vector可以用Point来表示 
struct Point{
	double x,y;
	Point(double _x=0,double _y=0):x(_x),y(_y){}
	//相等
	friend bool operator ==(const Point &a,const Point &b){
		return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
	}
	//不相等 
	friend bool operator !=(const Point &a,const Point &b){
		return !(a==b);
	}
	//相加 
	friend Point operator + (const Point &a,const Point &b){
		return Point(a.x+b.x,a.y+b.y);
	}
	//相减 
	friend Point operator - (const Point &a,const Point &b){
		return Point(a.x-b.x,a.y-b.y);
	}
	//点积 
	friend double operator * (const Point &a,const Point &b){
		return a.x*b.x+a.y*b.y;
	}
	//叉积 
	friend double operator % (const Point &a,const Point &b){
		return a.x*b.y-a.y*b.x;
	}
	//长度 
	inline double len(){
		return sqrt(x*x+y*y);
	}
	//单位向量
	Point unit(){
		double l=len();
		return Point(x/l,y/l);
	} 
	//求单位法向量 
	inline Point normal(){
		double l=len();
		return Point(-y/l,x/l);
	}
	//点从下往上排序
	inline bool operator < (Point b){
		return fabs(y-b.y)<eps?x<b.x:y<b.y; 
	} 
	//平面直角坐标系上半部分优先
	inline bool Quad(){
		return y>eps||(fabs(y)<=eps&&x>=-eps);
	} 
};
inline Point operator * (double k,Point a){
	return Point(a.x*k,a.y*k);
}
//两个向量的夹角 
inline double Angle(Point a,Point b){
	//return acos(a*b/a.len()/b.len());
	double tmp=atan2(b.y,b.x)-atan2(a.y,a.x); 
	while(tmp>=PI+eps)tmp-=2*PI;
	while(tmp<=-PI-eps)tmp+=2*PI;
	return tmp;
}
//判断两个向量是否平行
inline bool Para(Point a,Point b){
	return fabs(a%b)<=eps;
} 
//判断向量a是否在向量b的左侧
inline bool Left(Point a,Point b){
	return b%a>eps;
} 
//逆时针旋转p后的向量 
inline Point Rotate(Point a,double p){
	return Point(a.x*cos(p)-a.y*sin(p),a.x*sin(p)+a.y*cos(p));
}
//绕LTL逆时针排序 

//直线 
struct Line{
	Point p[2];
	Line(Point a=Point(0,0),Point b=Point(0,0)){p[0]=a,p[1]=b;}
	inline Point& operator [] (int i){
		return p[i];
	}
	inline Point v(){
		return p[1]-p[0];
	}
};
//直线交点 
inline Point Cross(Line a,Line b){
	return a[0]+((b[0]-a[0])%(b[1]-a[0]))/((a[1]-a[0])%(b[1]-b[0]))*(a[1]-a[0]);
} 
//多边形 
typedef vector<Point> Poly;
//面积 
double Area(Poly A){
	double tot=0;
	for(int i=0;i<(int)A.size()-1;++i){
		tot+=A[i]%A[i+1];
	}
	tot+=A[(int)A.size()-1]%A[0];
	return fabs(tot)/2.0;
} 
//周长
double C(Poly A){
	double tot=0;
	for(int i=0;i<(int)A.size()-1;++i){
		tot+=(A[i+1]-A[i]).len();
	}
	tot+=(A[A.size()-1]-A[0]).len();
	return tot;
} 
//重心 
Point Cent(Poly A){
	double x=0,y=0,m=0;
	for(int i=1;i<(int)A.size()-1;++i){
		double tmp=(A[i]-A[0])%(A[i+1]-A[0]);
		x+=tmp*(A[0].x+A[i].x+A[i+1].x)/3.0;
		y+=tmp*(A[0].y+A[i].y+A[i+1].y)/3.0;
		m+=tmp;
	}
	return Point(x/m,y/m);
} 
//求凸包
Poly Convex(Poly A){
	Point LTL=(*min_element(A.begin(),A.end())); //Lower Then Left
	sort(A.begin(),A.end(),[&](Point a,Point b){
		a=a-LTL,b=b-LTL;
		return Para(a,b)?a.len()<b.len():Left(b,a);
	});
	Poly st;
	for(auto p:A){
		while(st.size()>1&&!Left(p-st[(int)st.size()-2],st.back()-st[(int)st.size()-2]))st.pop_back();
		st.push_back(p);
	}
	return st;
}
// 求点是否在多边形内(单次询问,可以是凹多边形)
inline bool Inside_1(Poly A,Point p){
	double tot=0;
	for(int i=0;i<(int)A.size();++i)tot+=Angle(A[i]-p,A[(i+1)%A.size()]-p);
	return fabs(tot)>=eps;
} 
//多组询问
inline bool Inside_2(Poly &A,Point p){
	if(p==A[0])return true;
	if(Left(p-A[0],A[A.size()-1]-A[0])||Left(A[1]-A[0],p-A[0]))return false; 
	int pos=lower_bound(A.begin(),A.end()-1,p,[&](Point a,Point b){
		a=a-A[0],b=b-A[0];
		return Para(a,b)?a.len()<b.len():Left(b,a);
	})-A.begin();
	return !Left(A[pos]-A[pos-1],p-A[pos-1])&&A[0]<p;
}
//半平面交(HalfPlaneIntersection) <向量左侧> 
inline bool cmpang(Point a,Point b){
	return a.Quad()^b.Quad()?a.Quad()<b.Quad():Left(b,a);
}
inline bool operator <(Line a,Line b){
	return Para(a.v(),b.v())&&(a.v()*b.v()>eps)?Left(a[0]-b[0],b.v()):cmpang(a.v(),b.v());
}
Poly HPI(vector<Line> L){
	L.emplace_back(Point(-inf,-inf),Point(inf,-inf));
	L.emplace_back(Point(inf,-inf),Point(inf,inf));
	L.emplace_back(Point(inf,inf),Point(-inf,inf));
	L.emplace_back(Point(-inf,inf),Point(-inf,-inf));
	vector<Line> q(L.size()+10);
	static int l,r;
	sort(L.begin(),L.end());
	Poly R;
	r=1,q[l=1]=L[0];
	for(int i=1;i<(int)L.size();++i){
		if(Para(q[r].v(),L[i].v()))continue;
		while(l<r&&Left(L[i].v(),Cross(q[r],q[r-1])-L[i][0]))--r;
		while(l<r&&Left(L[i].v(),Cross(q[l],q[l+1])-L[i][0]))++l;
		q[++r]=L[i];
	}
	while(l<r&&Left(q[l].v(),Cross(q[r],q[r-1])-q[l][0]))--r;
	while(l<r&&Left(q[r].v(),Cross(q[l],q[l+1])-q[r][0]))++l;
	if(l==r)return R;
	q[r+1]=q[l];
	for(int i=l;i<=r;++i){
		R.push_back(Cross(q[i],q[i+1]));
	}
	return R;
}

//Minkowski
inline Poly operator + (const Poly &A,const Point &p){
	Poly C=A;
	for(auto &t:C)t=t+p;
	return C;
}
inline Poly operator + (const Poly &A,const Poly &B){
	if(A.empty())return B;
	if(B.empty())return A;
	if(A.size()==1)return B+A[0];
	if(B.size()==1)return A+B[0];
	Poly R;
	int i=0,j=0;
	R.push_back(A[0]+B[0]);
	while(true){
		Point vA=A[(i+1)%A.size()]-A[i],vB=B[(j+1)%B.size()]-B[j];
		if(Para(vA,vB)?vA.Quad()==vB.Quad():Left(vA,vB)){
			i=(i+1)%A.size();
		}
		else{
			j=(j+1)%B.size();
		}
		R.push_back(A[i]+B[j]);
		if(!i&&!j)break; 
	}
	R.pop_back();
	return R;
}
int n;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.setf(ios::fixed);
	cout.precision(10);
	vector<Line> L;
	cin>>n;
	Poly A(n);
	for(int i=0;i<n;++i){
		cin>>A[i].x>>A[i].y;
	}
	for(int i=0;i<n;++i){
		L.emplace_back(A[(i+1)%n],A[i]);
	}
	cout<<Area(HPI(L))<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3696kb

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: 2ms
memory: 3836kb

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: 2ms
memory: 3848kb

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: 2ms
memory: 3740kb

input:

3
198 165
322 122
242 84

output:

4076.0000000000

result:

ok "4076.000000000"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3764kb

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: 2ms
memory: 3696kb

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: 2ms
memory: 3800kb

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: 1ms
memory: 3688kb

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: 2ms
memory: 3840kb

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: 2ms
memory: 3864kb

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.1250000000

result:

ok "77922149990018.218750000"

Test #11:

score: 0
Accepted
time: 3ms
memory: 3936kb

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.0781250000

result:

ok "78537708558542.031250000"

Test #12:

score: 0
Accepted
time: 18ms
memory: 8992kb

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.6093750000

result:

ok "78539327974559.937500000"

Test #13:

score: 0
Accepted
time: 114ms
memory: 30864kb

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.2343750000

result:

ok "78525334096415.250000000"

Test #14:

score: 0
Accepted
time: 232ms
memory: 58124kb

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.8593750000

result:

ok "78479009888752.796875000"

Test #15:

score: 0
Accepted
time: 2ms
memory: 3824kb

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.5527343750

result:

ok "11331974361764.560546875"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3936kb

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.1289062500

result:

ok "302585512646.140625000"

Test #17:

score: 0
Accepted
time: 20ms
memory: 8840kb

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.1425781250

result:

ok "121175133.132812500"

Test #18:

score: 0
Accepted
time: 132ms
memory: 30708kb

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.0546875000

result:

ok "4772368.076171875"

Test #19:

score: 0
Accepted
time: 248ms
memory: 58128kb

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.6074218750

result:

ok "1169025.593750000"

Test #20:

score: 0
Accepted
time: 1ms
memory: 3816kb

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.0000000000

result:

ok "6435.000000000"

Test #21:

score: 0
Accepted
time: 0ms
memory: 3852kb

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.1000000000

result:

ok "4180.100000000"

Test #22:

score: 0
Accepted
time: 2ms
memory: 3888kb

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.0000000000

result:

ok "708179.000000000"

Test #23:

score: 0
Accepted
time: 2ms
memory: 3812kb

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.0758658010

result:

ok "696280.075865801"

Test #24:

score: 0
Accepted
time: 3ms
memory: 4072kb

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.0000000000

result:

ok "73741747.000000000"

Test #25:

score: 0
Accepted
time: 0ms
memory: 3892kb

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.0762995631

result:

ok "73705049.076299563"

Test #26:

score: 0
Accepted
time: 6ms
memory: 4488kb

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.0000000000

result:

ok "7448951491.000000000"

Test #27:

score: 0
Accepted
time: 0ms
memory: 4464kb

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.5340909958

result:

ok "7448332528.534090042"

Test #28:

score: 0
Accepted
time: 22ms
memory: 8580kb

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.0000000000

result:

ok "741575176515.000000000"

Test #29:

score: 0
Accepted
time: 21ms
memory: 8580kb

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.7573242188

result:

ok "741573412548.757324219"

Test #30:

score: 0
Accepted
time: 70ms
memory: 28368kb

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.0000000000

result:

ok "74106620545235.000000000"

Test #31:

score: 0
Accepted
time: 81ms
memory: 27460kb

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.8750000000

result:

ok "74103087971323.890625000"

Test #32:

score: -100
Runtime Error

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:


result: