QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#280780#7783. Military Maneuverucup-team266#TL 0ms3924kbC++204.5kb2023-12-09 17:54:172023-12-09 17:54:32

Judging History

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

  • [2023-12-09 17:54:32]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3924kb
  • [2023-12-09 17:54:17]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ld double
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
#define head l
#define tail r
void die(string S){puts(S.c_str());exit(0);}
const ld eps=1e-12;
int x[2020],y[2020];
struct Point
{
	ld x,y;
	Point(){}
	Point(ld _x,ld _y):x(_x),y(_y){}
	friend Point operator -(Point a,Point b)
	{
		return Point{a.x-b.x,a.y-b.y};
	}
	friend ld operator *(Point a,Point b)
	{
		return a.x*b.y-a.y*b.x;
	}
	friend bool operator ==(Point a,Point b)
	{
		return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
	}
	friend Point operator *(ld a,Point b)
	{
		return Point{a*b.x,a*b.y};
	}
	friend ld sqrd(Point x)
	{
		return x.x*x.x+x.y*x.y;
	}
	friend ld sqrd(Point a,Point b)
	{
		return sqrd(a-b);
	}
	friend ld dist(Point a,Point b)
	{
		return sqrtl(sqrd(a,b));
	}
};
ld atan2_kevin(Point p){return atan2l(p.y,p.x);}
struct Line
{
	Point a,b;
	Line(){}
	Line(Point _a,Point _b):a(_a),b(_b){}
	friend bool operator <(Line a,Line b)
	{
		ld t1=atan2_kevin(a.b-a.a);
		ld t2=atan2_kevin(b.b-b.a);
		if(fabs(t1-t2)>eps) return t1<t2;
		return (b.a-a.a)*(b.b-a.a)>eps;
	}
	friend bool operator ==(Line a,Line b)
	{
		return a.a==b.a&&a.b==b.b;
	}
};
Point its(Line a,Line b)
{
	ld v1=(b.b-b.a)*(a.b-b.b);
	ld v2=(b.b-b.a)*(a.b-a.a);
	ld T=v1/v2;
	return a.b-T*(a.b-a.a);
}
Point sw(Point x)
{
	return Point(x.y,-x.x);
}
Point cvh[2020];
Line lns[2020];
int head,tail;
ld calc2(Point a,Point b)
{
	ld S2=b*a;
	ld lsq=sqrd(a,b);
	ld l=sqrtl(lsq);
	ld retx=S2*S2/lsq*S2/4;
	ld rety1=S2*lsq/12;
	Point perp=its(Line(a,b),Line(Point(0,0),sw(b-a)));
	ld la=dist(perp,a);
	ld lb=dist(perp,b);
	if(fabs(la+lb-l)<eps)
		la=-la;
	ld rety2=S2*la*lb/4;
//	cerr<<"("<<a.x<<","<<a.y<<")"<<endl;
//	cerr<<"("<<b.x<<","<<b.y<<")"<<endl;
//	cerr<<S2<<" "<<l<<" "<<retx<<" "<<rety1<<" "<<rety2<<endl;
	return retx+rety1+rety2;
}
ld calc(vector<Line> vec,Point center)
{
	srt(vec);
	head=tail=0;
	int n=sz(vec);
	uni(vec);
//	for(auto v:vec)
//		cerr<<"("<<v.a.x<<","<<v.a.y<<"),("<<v.b.x<<","<<v.b.y<<")"<<endl;
	for(int i=0;i<n;i++)
	{
		while(tail-head>1&&(vec[i].b-cvh[r])*(vec[i].a-cvh[r])>-eps)
			r--;
		while(tail-head>1&&(vec[i].b-cvh[l+2])*(vec[i].a-cvh[l+2])>-eps)
			l++;
		lns[++r]=vec[i];
		if(tail-head>1) cvh[r]=its(lns[r],lns[r-1]);
	}
	while(tail-head>1&&(lns[l+1].b-cvh[r])*(lns[l+1].a-cvh[r])>-eps)
		r--;
	if(tail-head<3) return 0;
	cvh[l+1]=its(lns[l+1],lns[r]);
//	for(int i=l+1;i<=r;i++)
//		cerr<<cvh[i].x<<" "<<cvh[i].y<<endl;
	cvh[r+1]=cvh[l+1];
	ld ret=0.0;
	for(int i=l+1;i<=r;i++)
		ret+=calc2(cvh[i+1]-center,cvh[i]-center);
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	x1*=2;
	y1*=2;
	x2*=2;
	y2*=2;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
		x[i]*=2;
		y[i]*=2;
	}
	ld ans=0.0;
	for(int i=1;i<=n;i++) // expected dist squared when Pi is nearest
	{
		vector<Line> vec;
		vec.pb(Point{x1,y2},Point{x1,y1});
		vec.pb(Point{x2,y2},Point{x1,y2});
		vec.pb(Point{x2,y1},Point{x2,y2});
		vec.pb(Point{x1,y1},Point{x2,y1});
		for(int j=1;j<=n;j++) if(j!=i)
		{
			int mx=(x[i]+x[j])/2,my=(y[i]+y[j])/2;
			int dx=(x[j]-x[i])/2,dy=(y[j]-y[i])/2;
			vec.pb(Point{mx,my},Point{mx-dy,my+dx});
		}
		ans-=calc(vec,Point(x[i],y[i]));
//		cerr<<ans<<endl;
	}
	for(int i=1;i<=n;i++) // expected dist squared when Pi is farthest
	{
		vector<Line> vec;
		vec.pb(Point{x1,y2},Point{x1,y1});
		vec.pb(Point{x2,y2},Point{x1,y2});
		vec.pb(Point{x2,y1},Point{x2,y2});
		vec.pb(Point{x1,y1},Point{x2,y1});
		for(int j=1;j<=n;j++) if(j!=i)
		{
			int mx=(x[i]+x[j])/2,my=(y[i]+y[j])/2;
			int dx=(x[j]-x[i])/2,dy=(y[j]-y[i])/2;
			vec.pb(Point{mx,my},Point{mx+dy,my-dx});
		}
		ans+=calc(vec,Point(x[i],y[i]));
//		cerr<<ans<<endl;
	}
	ans/=(x2-x1);
	ans/=(y2-y1);
	ans/=4;
	ans*=acosl(-1.0);
	printf("%.15lf\n",ans);
	return 0;
}

详细

Test #1:

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

input:

0 0 2 2
2
3 1
1 3

output:

8.377580409572783

result:

ok found '8.3775804', expected '8.3775804', error '0.0000000'

Test #2:

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

input:

0 0 2 2
2
5 1
1 3

output:

37.699111843077517

result:

ok found '37.6991118', expected '37.6991118', error '0.0000000'

Test #3:

score: -100
Time Limit Exceeded

input:

-2911 2151 336 5941
2000
-83 79
-94 47
48 -29
-47 64
84 75
-44 -86
-58 -11
-31 58
20 53
80 -19
-82 74
-60 -26
8 -68
-42 -61
-14 12
-58 -18
92 10
35 -26
71 64
76 89
-80 6
70 4
-96 -99
95 -80
-3 -22
71 -89
-75 17
-35 -82
-59 95
60 48
-74 50
-82 90
-26 5
-75 -31
-45 85
85 14
-70 -57
59 46
55 13
-23 60
...

output:


result: