QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#368411#8513. Insects, Mathematics, Accuracy, and Efficiencyucup-team134#WA 22ms4360kbC++172.7kb2024-03-27 03:27:032024-03-27 03:27:04

Judging History

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

  • [2024-03-27 03:27:04]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:4360kb
  • [2024-03-27 03:27:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ldb double
#define pb push_back
#define mp make_pair

struct pt{
	ldb x,y;

	pt():x(0),y(0){}
	pt(ldb a,ldb b):x(a),y(b){}
};

pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator - (pt a){return pt(-a.x,-a.y);}
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator * (pt a,ldb b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,ldb b){return pt(a.x/b,a.y/b);}

pt perp(pt a){return pt(-a.y,a.x);}
ldb cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
ldb dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
ldb abs(pt a){return sqrt(dot(a,a));}

int part(pt a){return a.y<0 || (a.y==0 && a.x<0);}

bool operator < (pt a,pt b){return tie(a.x,a.y)<tie(b.x,b.y);}

const int N=10050;
pt pts[N];
vector<pt> ConvexHull(int n){
	sort(pts+1,pts+1+n);
	vector<pt> hull;
	int sz=0;
	for(int t=0;t<2;t++){
		int was=sz;
		for(int i=1;i<=n;i++){
			while(sz>was+1 && cross(hull[sz-1]-hull[sz-2],pts[i]-hull[sz-2])<=0){
				hull.pop_back();
				sz--;
			}
			hull.pb(pts[i]);
			sz++;
		}
		hull.pop_back();
		sz--;
		reverse(pts+1,pts+1+n);
	}
	return hull;
}

void Inter(pt a,pt b,ldb r,vector<pt>& cand){
	pt v=b-a;
	ldb d=cross(v,a)/abs(v);
	pt h=-perp(v);
	h=h/abs(h)*d;
	ldb len=sqrt(max(0.0,r*r-d*d));
	cand.pb(h+v/abs(v)*len);
	cand.pb(h-v/abs(v)*len);
}

int main(){
	int n,r;
	scanf("%i %i",&n,&r);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%i %i",&x,&y);
		pts[i]=pt(x,y);
	}
	vector<pt> hull=ConvexHull(n);
	if(hull.size()<2){
		printf("0.0\n");
		return 0;
	}
	vector<pt> cand;
	for(int i=0;i<hull.size();i++){
		Inter(hull[i],hull[(i+1)%hull.size()],r,cand);
		Inter(pt(0,0),perp(hull[i]-hull[(i+1)%hull.size()]),r,cand);
	}
	//printf("Hull ");
	//for(pt p:hull)printf("(%lf, %lf) ",p.x,p.y);
	//printf("\n");
	sort(cand.begin(),cand.end(),[&](pt a,pt b){return mp(part(a),0.0)<mp(part(b),cross(a,b));});
	int L=0,R=0;
	auto nxt=[&](int x){return (x+1)%hull.size();};
	auto pre=[&](int x){return (x-1+hull.size())%hull.size();};
	ldb ans=0;
	for(int i=0;i<hull.size();i++){
		ans+=cross(hull[i],hull[nxt(i)]);
	}
	ans=abs(ans)/2;
	for(pt p:cand){
		//printf("(%lf, %lf)\n",p.x,p.y);
		while(cross(hull[L]-p,hull[nxt(L)]-p)<0)L=nxt(L);
		while(cross(hull[L]-p,hull[pre(L)]-p)<0)L=pre(L);
		while(cross(hull[R]-p,hull[nxt(R)]-p)>0)R=nxt(R);
		while(cross(hull[R]-p,hull[pre(R)]-p)>0)R=pre(R);
		//printf("L(%lf, %lf) R(%lf, %lf)\n",hull[L].x,hull[L].y,hull[R].x,hull[R].y);
		ldb now=0;
		for(int i=L;i!=R;i=nxt(i)){
			now+=cross(hull[i],hull[nxt(i)]);
		}
		now+=cross(hull[R],p);
		now+=cross(p,hull[L]);
		now=abs(now)/2;
		//printf("%lf\n",now);
		ans=max(ans,now);
	}
	printf("%.12lf\n",ans);
	return 0;
}

詳細信息

Test #1:

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

input:

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

output:

2000000.000000000000

result:

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

Test #2:

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

input:

2 100
17 7
19 90

output:

4849.704644437563

result:

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

Test #3:

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

input:

1 100
13 37

output:

0.0

result:

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

Test #4:

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

input:

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

output:

2240000.000000000000

result:

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

Test #5:

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

input:

3 1000
200 400
-600 -400
400 -800

output:

1045685.424949237844

result:

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

Test #6:

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

input:

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

output:

732310.562561766012

result:

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

Test #7:

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

input:

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

output:

892213.595499957912

result:

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

Test #8:

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

input:

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

output:

619005.494464025949

result:

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

Test #9:

score: -100
Wrong Answer
time: 22ms
memory: 4360kb

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:

314026590.136600553989

result:

wrong answer 1st numbers differ - expected: '314026591.7801104', found: '314026590.1366006', error = '0.0000000'