小凸想跑步
小凸晚上喜欢到操场跑步，今天他跑完两圈之后，他玩起了这样一个游戏。
操场是个凸(n)边形，(n)个顶点按照逆时针从(0 sim n - 1)编号。现在小凸随机站在操场中的某个位置，标记为(p)点。将(p)点与(n)个顶点各连一条边，形成(n)个三角形。如果这时(p)点，(0)号点，(1)号点形成的三角形的面积是(n)个三角形中最小的一个，小凸则认为这是一次正确站位。
现在小凸想知道他一次站位正确的概率是多少。
(3 leq n leq 10 ^ 5, -10 ^ 9 leq x, y leq 10 ^ 9)。
题解
https://www.cnblogs.com/cj-xxz/p/10603286.html
对每个三角形面积列不等式跑半平面交即可。
假设多边形边上四个点逆时针依次是(a,b,c,d)，要求范围的点是(p)。
[(b-a) imes (p-a)leq (d-c) imes (p-c)
]
[(x_b-x_a,y_b-y_a) imes (x_p-x_a,y_p-y_a)leq (x_d-x_c,y_d-y_c) imes (x_p-x_c,y_p-y_c)
]
[(x_b-x_a-x_d+x_c)y_p-(y_b-y_a-y_d+y_c)x_p-x_by_a+y_bx_a+x_dy_c-y_dx_cleq 0
]
根据不等式就能确定半平面。
时间复杂度(O(nlog n))。
CO float128 eps=1e-9;
struct point {float128 x,y;};
IN point operator+(CO point&a,CO point&b){
return {a.x+b.x,a.y+b.y};
}
IN point operator-(CO point&a,CO point&b){
return {a.x-b.x,a.y-b.y};
}
IN point operator*(CO point&a,float128 b){
return {a.x*b,a.y*b};
}
IN point operator/(CO point&a,float128 b){
return {a.x/b,a.y/b};
}
IN float128 dot(CO point&a,CO point&b){
return a.x*b.x+a.y*b.y;
}
IN float128 cross(CO point&a,CO point&b){
return a.x*b.y-a.y*b.x;
}
struct line {point x,y;};
IN float128 angle(CO line&a){
return atan2(a.y.y,a.y.x);
}
IN bool on_left(CO point&a,CO line&b){
return cross(b.y,a-b.x)>0;
}
IN point intersect(CO line&a,CO line&b){
return b.x+b.y*cross(b.x-a.x,a.y)/cross(a.y,b.y);
}
CO int N=2e5+10;
point p[N];
line ln[N];
int main(){
int n=read<int>();
for(int i=1;i<=n;++i) read(p[i].x),read(p[i].y);
p[n+1]=p[1];
int m=0;
float128 area=0;
for(int i=1;i<=n;++i){
ln[++m]={p[i],p[i+1]-p[i]};
area+=cross(p[i],p[i+1]);
}
for(int i=2;i<=n;++i){
float128 a=p[2].x-p[1].x-p[i+1].x+p[i].x;
float128 b=p[2].y-p[1].y-p[i+1].y+p[i].y;
float128 c=-p[2].x*p[1].y+p[2].y*p[1].x+p[i+1].x*p[i].y-p[i+1].y*p[i].x;
if(a) ln[++m]={{0,-c/a},{-a,-b}};
else if(b) ln[++m]={{c/b,0},{-a,-b}};
}
sort(ln+1,ln+m+1,[&](CO line&a,CO line&b)->bool{
return angle(a)<angle(b);
});
int l,r=1;
for(int i=2;i<=m;++i){
if(abs(angle(ln[i])-angle(ln[r]))>eps) ln[++r]=ln[i];
else if(on_left(ln[i].x,ln[r])) ln[r]=ln[i];
}
m=r,l=r=1;
for(int i=2;i<=m;++i){
for(;l<r and !on_left(p[r],ln[i]);--r);
for(;l<r and !on_left(p[l+1],ln[i]);++l);
ln[++r]=ln[i];
if(l<r) p[r]=intersect(ln[r-1],ln[r]);
}
for(;l<r and !on_left(p[r],ln[l]);--r);
p[l]=p[r+1]=intersect(ln[r],ln[l]);
float128 ans=0;
for(int i=l;i<=r;++i) ans+=cross(p[i],p[i+1]);
ans/=area;
printf("%.4Lf
",ans);
return 0;
}