QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#279414#7783. Military Maneuverucup-team1447#WA 3010ms14112kbC++145.6kb2023-12-08 17:59:482023-12-08 17:59:48

Judging History

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

  • [2023-12-08 17:59:48]
  • 评测
  • 测评结果:WA
  • 用时:3010ms
  • 内存:14112kb
  • [2023-12-08 17:59:48]
  • 提交

answer

/*  Never Island  */
/*deco loves Chino*/
#include <bits/stdc++.h>
#define double long double
double sh;
using namespace std;
const double eps=1e-13;
int n,m;
double x[1234567],y[1234567];

inline int read()
{
    int num=0,f=1;char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)num=num*10+(c^48),c=getchar();
    return num*f;
}
double xl=read(),yl=read(),xr=read(),yr=read();
namespace qwq{
#define QAQ int
#define TAT long long
#define OwO bool
#define F(i,j,n) for(QAQ i=j;i<=n;++i)
#define E(i,j,n) for(QAQ i=j;i>=n;--i)
#define MES(i,j) memset(i,j,sizeof(i))
#define MEC(i,j) memcpy(i,j,sizeof(j))

using namespace std;
const int N=40005;
const double eps=1e-9;

struct Point{
	double x,y;
	
	friend Point operator - (Point a,Point b){
		Point t;
		t.x=a.x-b.x;t.y=a.y-b.y;
		return t;
	}
	friend Point operator + (Point a,Point b){
		Point t;
		t.x=a.x+b.x;t.y=a.y+b.y;
		return t;
	}
	friend double operator * (Point a,Point b){
		return a.x*b.x+a.y*b.y;
	}
	friend double operator ^ (Point a,Point b){
		return a.x*b.y-b.x*a.y;
	}
	friend Point operator * (double k,Point b){
		Point t;
		t.x=k*b.x;t.y=k*b.y;
		return t; 
	}
}b[N];
int sign(double x){
	return fabs(x)<=eps ?  0 : (x>0 ? 1 : -1);
}
struct Line{
	Point p,v;
	Line(Point x,Point y):p(x),v(y){}
	Line(){}
	double poa;
	friend OwO operator < (Line x,Line y){
		return sign(x.poa-y.poa)==0 ? sign((x.v-x.p) ^ (y.v-x.p)) >0 : sign(x.poa-y.poa)<0;
		//因为我是向量左侧求交,所以极角相同时靠左的更优,把优的放在后面,方便之后的操作 ,可以画图体会一下 
	}
}a[N],q[N];
int js,cnt,head,tail;
double ans;

Point inter(Line a,Line b){//求交点 
	Point p1=a.p,p2=b.p,v1=a.v,v2=b.v;
	v1=v1-p1;v2=v2-p2;
	Point u=p2-p1;
	// if(fabs(u^v1)<eps)return p2;
	// assert(fabs((v1^v2))>eps);
	Point p=p2+((u^v1)/(v1^v2))*v2;
	return p;
}

OwO pd(Line i,Line j,Line k){
	// assert(fabs(i.v-i.p^j.v-j.p)>eps);
	Point p=inter(i,j);
	return sign((k.v-k.p) ^ (p-k.p))<eps;
}

void Half_Plane(){
	sort(a+1,a+js+1);//排序 
	cnt=0;
	F(i,1,js) {
		if(sign(a[i].poa-a[i-1].poa)!=0) cnt++;
		a[cnt]=a[i];//因为排过序,即使极角相同,后面的也比前面的优 
	}
	head=1;tail=0;
	q[++tail]=a[1];q[++tail]=a[2];
	F(i,3,cnt){
		while(head<tail&&pd(q[tail-1],q[tail],a[i])) tail--;//维护双端队列 
		while(head<tail&&pd(q[head+1],q[head],a[i])) head++;
		q[++tail]=a[i];
	}
	while(head<tail&&pd(q[tail-1],q[tail],q[head])) tail--;
	while(head<tail&&pd(q[head+1],q[head],q[tail])) head++;
	q[tail+1]=q[head];
	js=0;
	F(i,head,tail) b[++js]=inter(q[i],q[i+1]);
}

int main(int v,int tp)
{
	// int n;
	// cin>>n;
	int &sum=js;
	sum=0;
	// for(int i=1;i<=n;i++)
	// {
		// cin>>m;
		// for(int j=1;j<=m;j++)
		// {
			// scanf("%lf%lf",&Q[j].x,&Q[j].y);
		// }
		// 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]);
		// }
	// }
	a[++sum]=Line({xl,yl},{1,0});
	a[++sum]=Line({xr,yl},{0,1});
	a[++sum]=Line({xr,yr},{-1,0});
	a[++sum]=Line({xl,yr},{0,-1});
	for(int i=1;i<v;i++)
		if(x[i]==x[v]&&y[i]==y[v])return 0;
	for(int i=1;i<=n;i++)
	{
		if(x[i]==x[v]&&y[i]==y[v])continue;
		double p=(x[i]+x[v])/2,q=(y[i]+y[v])/2;
		double r=(x[i]-x[v]),s=(y[i]-y[v]);
		std::swap(r,s);
		if(tp)s=-s;else r=-r;
		a[++sum]=Line({p,q},{r,s});
	}
	F(i,1,js) a[i].poa=atan2(a[i].v.y-a[i].p.y,a[i].v.x-a[i].p.x);
	F(i,1,js)a[i].v.x*=1e0,a[i].v.y*=1e0;
	F(i,1,js)a[i].v.x+=a[i].p.x,a[i].v.y+=a[i].p.y;
	Half_Plane();
	b[js+1]=b[1];
	double tmp=0;
	if(js>2) 
	{
	// for(int i=head;i<=tail;i++)printf("%.3lf %.3lf %.3lf %.3lf \n",q[i].p.x,q[i].p.y,q[i].v.x,q[i].v.y);
	// for(int i=head;i<=tail;i++)printf("%.3lf %.3lf\n",b[i].x,b[i].y);
	// puts("");
		double d=x[v];
		for(int i=head;i<=tail;i++)
		{
			auto [l,x]=b[i];
			auto [r,y]=b[i==tail?head:i+1];
			if(fabs(r-l)<eps)continue;
			double k=(y-x)/(r-l),b=x-l*k;
			double f4=k/4;
			double f3=(b-2*d*k)/3;
			double f2=(d*k-2*b)*d/2;
			double f1=d*d*b;
			auto calc=[&](double t)
			{
				return t*t*t*t*f4+t*t*t*f3+t*t*f2+t*f1;
			};
			double v=calc(r)-calc(l);
			if(tp)v=-v;
			sh+=v;
			// printf("(%d %.3lf %.3lf)ans+=%.12lf\n",i,k,b,v);
		}
		// puts("xx");
	}
	if(js>2) 
	{
	// for(int i=head;i<=tail;i++)printf("%.3lf %.3lf %.3lf %.3lf \n",q[i].p.x,q[i].p.y,q[i].v.x,q[i].v.y);
	// for(int i=head;i<=tail;i++)printf("%.3lf %.3lf\n",b[i].x,b[i].y);
	// puts("");
	// puts("");
		double d=y[v];
		for(int i=head;i<=tail;i++)
		{
			auto [x,l]=b[i];
			auto [y,r]=b[i==tail?head:i+1];
			if(fabs(r-l)<eps)continue;
			double k=(y-x)/(r-l),b=x-l*k;
			double f4=k/4;
			double f3=(b-2*d*k)/3;
			double f2=(d*k-2*b)*d/2;
			double f1=d*d*b;
			auto calc=[&](double t)
			{
				return t*t*t*t*f4+t*t*t*f3+t*t*f2+t*f1;
			};
			// printf("%.3lfx^4+%.3lfx^3+%.3lfx^2+%.3lfx\n",f4,f3,f2,f1);
			double v=calc(r)-calc(l);
			if(!tp)v=-v;
			// printf("ansy+=%.12lf\n",v);
			sh+=v;
		}
		// puts("yy");
	}
	// F(i,1,js) tmp+=(b[i]^b[i+1]);
	// printf("%.3lf\n",tmp);
	// sort(a+1,P+sum+1);//极角排序
	// work();
	// solve();
	// puts("");
	return 0;
}

}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)x[i]=read(),y[i]=read();
	for(int i=1;i<=n;i++)qwq::main(i,0);
	for(int i=1;i<=n;i++)qwq::main(i,1);
	// printf("%.12l?f\n",sh);
	sh*=acosl(-1);
	printf("%.12Lf\n",sh/(xr-xl)/(yr-yl));
	// printf("%.12lf\n",8.377580409572781970/acos(-1));
	// printf("%.12lf\n",37.699111843077518863/acos(-1));
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 12052kb

input:

0 0 2 2
2
3 1
1 3

output:

8.377580409573

result:

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

Test #2:

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

input:

0 0 2 2
2
5 1
1 3

output:

37.699111843078

result:

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

Test #3:

score: -100
Wrong Answer
time: 3010ms
memory: 14112kb

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:

-nan

result:

wrong output format Expected double, but "-nan" found