- \(S(P,p_0,p_1)<S(P,p_i,p_{i+1})\) 这个约束条件对于 \(P_x,P_y\) 是线性的,即将面积用向量叉积表示,暴力拆开,可得到 \(aP_x+bP_y+c<0\) 的形式,表示了一个半平面,其他每条边都确定了一个半平面.
- 再将 \(P\) 在多边形内拆成 \(N-1\) 个半平面的限制,将这 \(2N-1\) 个半平面求交,得到的区域即为合法区域,除以总面积即得答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
fh=-1,jp=getchar();
while (jp>='0'&&jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*fh;
}
const double eps=1e-8;
inline int dcmp(double x)
{
if(fabs(x)<=eps)
return 0;
return x>0;
}
const int MAXN=2e5+10;
struct v2
{
double x,y;
v2(double x=0,double y=0):x(x),y(y) {}
friend double operator * (const v2 &a,const v2 &b)
{
return a.x*b.y-a.y*b.x;
}
v2 operator + (const v2 &rhs) const
{
return v2(x+rhs.x,y+rhs.y);
}
v2 operator - (const v2 &rhs) const
{
return v2(x-rhs.x,y-rhs.y);
}
v2 operator ^ (const double &lambda) const
{
return v2(x*lambda,y*lambda);
}
double modulus()
{
return sqrt(x*x+y*y);
}
double angle()
{
return atan2(y,x);
}
bool operator < (const v2 &rhs) const
{
return x==rhs.x?y<rhs.y:x<rhs.x;
}
};
struct Line
{
v2 p,v;
double angle()
{
return v.angle();
}
friend bool operator < (Line a,Line b)
{
if(a.angle()!=b.angle())
return a.angle()<b.angle();
return a.v*b.v<0;
}
};
bool Onleft(Line L,v2 p)
{
return (L.v*(p-L.p))>0;
}
v2 Intersection(Line a,Line b)
{
v2 u=a.p-b.p;
double t=(b.v*u)/(a.v*b.v);
return a.p+(a.v^t);
}
#define x(I) poly[I].x
#define y(I) poly[I].y
int n,totl=0;
v2 poly[MAXN];
Line L[MAXN],q[MAXN];
v2 p[MAXN];
int head,tail;
void Hpi()
{
sort(L+1,L+1+totl);
q[head=tail=1]=L[1];
for(int i=2;i<=totl;++i)
{
while(head<tail && !Onleft(L[i],p[tail-1]))
--tail;
while(head<tail && !Onleft(L[i],p[head]))
++head;
++tail;
q[tail]=L[i];
if(head<tail && (q[tail].v*q[tail-1].v)==0)
{
--tail;
if(Onleft(q[tail],L[i].p))
q[tail]=L[i];
}
if(head<tail)
p[tail-1]=Intersection(q[tail-1],q[tail]);
}
while(head<tail && !Onleft(q[head],p[tail-1]))
--tail;
p[tail]=Intersection(q[tail],q[head]);
p[tail+1]=p[head];
double area=0;
v2 O=v2(0,0);
for(int i=head;i<=tail;++i)
area+=(O-p[i])*(O-p[i+1]);
area=fabs(area);
double ts=0;
for(int i=1;i<=n;++i)
ts+=(O-poly[i])*(O-poly[i+1]);
ts=fabs(ts);
printf("%.4lf\n",area/ts);
}
int main()
{
n=read();
for(int i=1; i<=n; ++i)
scanf("%lf%lf",&poly[i].x,&poly[i].y);
poly[n+1]=poly[1];
for(int i=1; i<=n; ++i)
{
++totl;
L[totl].p=poly[i];
L[totl].v=poly[i+1]-poly[i];
}
for(int i=2; i<=n; ++i)
{
int j=i+1;
double a=x(2)-x(1),b=y(2)-y(1);
double c=x(j)-x(i),d=y(j)-y(i);
double A=d-b,B=a-c,C=b*x(1)-a*y(1)+c*y(i)-d*x(i);
if(A==0 && B==0)
{
if(C<=0)
continue;
else
return puts("0.0000")&0;
}
++totl;
if(A==0)
L[totl].p=v2(0,-C/B);
else
L[totl].p=v2(-C/A,0);
L[totl].v=v2(-B,A);
if(i!=n && !Onleft(L[totl],poly[1]))
L[totl].v=(L[totl].v^(-1));
if(i==n && !Onleft(L[totl],poly[2]))
L[totl].v=(L[totl].v^(-1));
}
Hpi();
return 0;
}