QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#454049#876. Big Brothergrass8cow#RE 1ms4400kbC++172.3kb2024-06-24 16:08:422024-06-24 16:08:44

Judging History

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

  • [2024-06-24 16:08:44]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:4400kb
  • [2024-06-24 16:08:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const double eps=1e-10;
int n,m,sum;
struct vec
{
	double x,y;
	vec(double X=0,double Y=0):x(X),y(Y){}
	vec operator+(const vec&a)const
	{
		return vec(x+a.x,y+a.y);
	}
	vec operator-(const vec&a)const
	{
		return vec(x-a.x,y-a.y);
	}
	void operator+=(const vec&a)
	{
		this->x+=a.x,this->y+=a.y;
	}
	void operator-=(const vec&a)
	{
		this->x-=a.x,this->y-=a.y;
	}
	vec operator*(const double&a)const
	{
		return vec(x*a,y*a);
	}
	vec operator/(const double&a)const
	{
		return vec(x/a,y/a);
	}
	void operator*=(const double&a)
	{
		this->x*=a,this->y*=a;
	}
	void operator/=(const double&a)
	{
		this->x/=a,this->y/=a;
	}
}Q[1100],M[1100];
double cp(vec A,vec B)//叉积
{
	return A.x*B.y-A.y*B.x;
}
double pp(vec A,vec B)//点积
{
	return A.x*B.x+A.y*B.y;
}
struct line
{
	vec A,B;
	double K;
	line(vec a,vec b):A(a),B(b){K=atan2(B.y,B.x);}//按极角排序
	line(){}
	bool operator<(const line&a)const
	{
		return K<a.K; 
	}
}P[1100],T[1100];
int st,en;
vec get(line A,line B)//求交点
{
	vec C=A.A-B.A;
	double t=cp(B.B,C)/cp(A.B,B.B);
	return A.A+A.B*t; 
}
void work()
{
	st=en=1;
	T[st]=P[1];
	for(int i=2;i<=sum;i++)
	{
		while(st<en&&cp(P[i].B,M[en-1]-P[i].A)<=eps)//踢出队尾,交点在当前边右侧
		{			
			--en;
		}
		while(st<en&&cp(P[i].B,M[st]-P[i].A)<=eps)//踢出队首,交点在当前边右侧
		{
			++st;
		}
		T[++en]=P[i]; 
		if(fabs(cp(T[en].B,T[en-1].B))<=eps)//平行
		{
			en--;
			if(cp(T[en].B,P[i].A-T[en].A)>eps)//取更左边那个
			{
				T[en]=P[i];
			}
		}
		if(st<en)//有多个边在集合中,加入交点
		{
			M[en-1]=get(T[en-1],T[en]);
		}
	}
	while(st<en&&cp(T[st].B,M[en-1]-T[st].A)<=eps)
	{
		--en;
	}
	if(en-st<=1)
	{
		return ;
	}
	M[en]=get(T[st],T[en]);
}
void solve()
{
	double ans=0;
	for(int i=st;i<=en;i++)//计算面积
	{
		int to=i+1;
		if(i==en)
		{
			to=st;
		}
		ans+=cp(M[i],M[to]);
	}
	printf("%.10lf",ans/2);
}
int main()
{
	int m;
		cin>>m;
		for(int j=1;j<=m;j++)
		{
			scanf("%lf%lf",&Q[j].x,&Q[j].y);
		}
        reverse(Q+1,Q+m+1);
		for(int j=1;j<=m;j++)
		{
			++sum;
			int to=j+1;
			if(j==m)
			{
				to=1;
			}
			P[sum]=line(Q[j],Q[to]-Q[j]);
		}
	sort(P+1,P+sum+1);//极角排序
	work();
	solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4240kb

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: 0ms
memory: 4224kb

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: 0ms
memory: 4376kb

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: 0ms
memory: 4400kb

input:

3
198 165
322 122
242 84

output:

4076.0000000000

result:

ok "4076.000000000"

Test #5:

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

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: 0ms
memory: 4328kb

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: 0ms
memory: 4328kb

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: 0ms
memory: 4364kb

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: 0ms
memory: 4392kb

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: 0ms
memory: 4388kb

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

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

result:

ok "78537708558542.031250000"

Test #12:

score: -100
Runtime Error

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:


result: