QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363018#8513. Insects, Mathematics, Accuracy, and Efficiencyucup-team052#RE 4ms4164kbC++232.4kb2024-03-23 17:55:122024-03-23 17:55:12

Judging History

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

  • [2024-03-23 17:55:12]
  • 评测
  • 测评结果:RE
  • 用时:4ms
  • 内存:4164kb
  • [2024-03-23 17:55:12]
  • 提交

answer

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#else
#define D(...) ((void)0)
#endif
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define pb push_back
using namespace std;
#define N 10005
struct Vec
{
	double x,y;
	Vec(double a=0,double b=0) {x=a,y=b;}
};
const double eps=1e-7;
int sgn(double x)
{
	if(x>eps) return 1;
	else if(x<-eps) return -1;
	return 0;
}
Vec operator + (const Vec &x,const Vec &y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (const Vec &x,const Vec &y) {return Vec(x.x-y.x,x.y-y.y);}
double cdot(const Vec &x,const Vec &y) {return x.x+y.x+x.y*y.y;}
double cross(const Vec &x,const Vec &y) {return x.x*y.y-x.y*y.x;}
double dis(const Vec &x) {return sqrt(x.x*x.x+x.y*x.y);}
int ccw(const Vec &x,const Vec &y,const Vec &z)
{
	int w=sgn(cross(y-x,z-x));
	return w;
}
Vec a[N];
int n,st[N+N],tp;
double ans,R;
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	cin>>n>>R;
	for(int i=1;i<=n;i++) scanf("%lf %lf",&a[i].x,&a[i].y);
	int mnx=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i].x<a[mnx].x) mnx=i;
	}
	swap(a[mnx],a[1]);
	sort(a+2,a+n+1,[&](const Vec &x,const Vec &y){
		return ccw(a[1],x,y)==-1||(ccw(a[1],x,y)==0&&dis(x-a[1])<dis(y-a[1]));
	});
	st[++tp]=1;
	for(int i=2;i<=n;i++)
	{
		while(tp>=2&&ccw(a[st[tp-1]],a[st[tp]],a[i])>=0) tp--;
		st[++tp]=i;
	}
	for(int i=1;i<=tp;i++) st[i+tp]=st[i];
	assert(tp<=1000);
	double S=0;
	for(int i=2;i<tp;i++) S+=cross(a[st[i+1]]-a[1],a[st[i]]-a[1]);
	S/=2;
//	for(int i=1;i<=tp;i++) printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
	for(int i=1;i<=tp;i++)
	{
		double siz=0;
		for(int j=i+1;j<i+tp;j++)
		{
			if(j!=i+1) siz+=cross(a[st[j]]-a[st[i]],a[st[j-1]]-a[st[i]])/2;
			double L=dis(a[st[i]]-a[st[j]]);
			double gv=R*L+cross(a[st[i]],a[st[j]]); gv/=2;
			ans=max(ans,S-siz+gv);
//			printf("%d %d : %lf %lf %lf\n",i,j,S,siz,gv);
		}
	}
	printf("%.10lf\n",ans);
	return 0;
}
/*
-1000.000000 0.000000
1000.000000 0.000000
0.000000 -1000.000000
1 2 : 1000000.000000 0.000000 1000000.000000
1 3 : 1000000.000000 1000000.000000 1207106.781187
2 3 : 1000000.000000 0.000000 207106.781187
2 4 : 1000000.000000 500000.000000 1000000.000000
3 4 : 1000000.000000 0.000000 207106.781187
3 5 : 1000000.000000 0.000000 1207106.781187
2207106.7811865476
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 1000
-1000 0
0 0
1000 0
0 -1000

output:

2000000.0000000000

result:

ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'

Test #2:

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

input:

2 100
17 7
19 90

output:

4849.7046444376

result:

ok found '4849.704644438', expected '4849.704644438', error '0.000000000'

Test #3:

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

input:

1 100
13 37

output:

0.0000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #4:

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

input:

4 1000
-800 600
800 600
-800 -600
800 -600

output:

2240000.0000000000

result:

ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'

Test #5:

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

input:

3 1000
200 400
-600 -400
400 -800

output:

1045685.4249492381

result:

ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'

Test #6:

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

input:

4 1000
200 -600
600 -400
800 -600
0 -800

output:

732310.5625617660

result:

ok found '732310.562561766', expected '732310.562561766', error '0.000000000'

Test #7:

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

input:

4 1000
-600 700
-300 900
0 800
-800 400

output:

892213.5954999579

result:

ok found '892213.595499958', expected '892213.595499958', error '0.000000000'

Test #8:

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

input:

5 1000
-300 -200
-200 -400
-100 -700
-800 -500
-500 -300

output:

619005.4944640258

result:

ok found '619005.494464026', expected '619005.494464026', error '0.000000000'

Test #9:

score: 0
Accepted
time: 4ms
memory: 4048kb

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314026591.7801103592

result:

ok found '314026591.780110359', expected '314026591.780110359', error '0.000000000'

Test #10:

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

input:

2 10000
-9999 0
-9998 -1

output:

12070.5678118655

result:

ok found '12070.567811865', expected '12070.567811865', error '0.000000000'

Test #11:

score: -100
Runtime Error

input:

1604 10000
2604 -9655
7380 -6748
9963 859
9843 1765
-1452 9894
-2024 9793
-8862 4633
-2604 -9655
9301 3673
9871 -1601
-565 -9984
9640 -2659
9312 3645
-8291 -5591
7879 6158
1301 9915
509 9987
7757 -6311
-9301 -3673
7702 -6378
5415 8407
-9971 761
9023 -4311
-6785 7346
-9852 1714
-9788 -2048
9819 -1894...

output:


result: