题目描述
小凸晚上喜欢到操场跑步，今天他跑完两圈之后，他玩起了这样一个游戏。
操场是个凸 n 边形， nn 个顶点按照逆时针从 0 ∼n−1 编号。现在小凸随机站在操场中的某个位置，标记为p点。将 p 点与 n个顶点各连一条边，形成 n个三角形。如果这时p 点， 0号点， 1号点形成的三角形的面 积是 n个三角形中最小的一个，小凸则认为这是一次正确站位。
现在小凸想知道他一次站位正确的概率是多少。
题解
我们其实是要找到一个p点，使得pp0*pp1<=ppi*ppi+1.
然后我们把上面的式子展开，然后化简，这个不难就是挺麻烦的。
最后得到了Ax+By+C<=0的形式，然后可以用(-1e9,y1)(1e9,y2)这条直线来描述这个限制，再加上凸多边形的限制，跑个半平面交就好了。
注意：要特判A或B=0的情况。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define N 200009
#define double long double
#define eq(x,y) (fabs((x)-(y))<eps)
using namespace std;
const double eps=1e-;
int n,top,tot;
double x[N],y[N],s,S;
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
struct point{
double x,y;
point(double xx=,double yy=){x=xx;y=yy;}
inline point operator +(const point &b)const{return point{x+b.x,y+b.y};}
inline point operator -(const point &b)const{return point{x-b.x,y-b.y};}
inline double operator *(const point &b)const{return x*b.y-y*b.x;}
inline point operator *(const double &b)const{return point{x*b,y*b};}
}p[N];
struct line{
point x,y;double ang;
line(double x1=,double x2=,double x3=,double x4=){x.x=x1;x.y=x2;y.x=x3;y.y=x4;}
bool operator <(const line &b)const{
if(fabs(ang-b.ang)<eps)return (y-x)*(b.x-x)<eps;
else return ang<b.ang;
}
}a[N],l[N],q[N];
inline bool left(point a,line b){return (a-b.x)*(b.y-b.x)>-eps;}
inline point jiao(line a,line b){return b.x+(b.y-b.x)*(((b.x-a.x)*(a.y-a.x))/((a.y-a.x)*(b.y-b.x)));}
int main(){
n=rd();
for(int i=;i<n;++i){
x[i]=rd(),y[i]=rd();
if(i)l[++top]=line(x[i-],y[i-],x[i],y[i]);
}
l[++top]=line(x[n-],y[n-],x[],y[]);
for(int i=;i<n;++i)S+=(point(x[i],y[i])-point(x[],y[]))*(point{x[i-],y[i-]}-point{x[],y[]})/;S=fabs(S);
x[n]=x[];y[n]=y[];
for(int i=;i<n;++i){
double a=-y[]+y[]+y[i+]-y[i],b=-x[]+x[]+x[i]-x[i+],c=x[]*y[]-x[]*y[]-x[i]*y[i+]+x[i+]*y[i];
if(fabs(b)<eps){
if(fabs(a)<eps){puts("0.0000");return ;}
double xf=-c/a,xs=xf,yf=,ys=1e15;
if(a<)l[++top]=line(xs,ys,xf,yf);
else l[++top]=line(xf,yf,xs,ys);
}
else{
double xf=-1e11,xs=1e11,yf=(-c-a*xf)/b,ys=(-c-a*xs)/b;
if(b>=){l[++top]=line(xs,ys,xf,yf);
}else l[++top]=line(xf,yf,xs,ys);
}
}
for(int i=;i<=top;++i)l[i].ang=atan2(l[i].y.y-l[i].x.y,l[i].y.x-l[i].x.x);
sort(l+,l+top+);
for(int i=;i<=top;++i)if(i==||fabs(l[i].ang-l[i-].ang)>eps)a[++tot]=l[i];
int h=,t=;q[]=a[];q[]=a[];p[]=jiao(a[],a[]);
for(int i=;i<=tot;++i){
while(h<t&&left(p[t-],a[i]))t--;
while(h<t&&left(p[h],a[i]))h++;
q[++t]=a[i];p[t-]=jiao(q[t-],q[t]);
}
while(h<t&&left(p[h],q[t]))h++;
while(h<t&&left(p[t-],q[h]))t--;
p[t]=jiao(q[t],q[h]);
for(int i=h+;i<=t;++i)s+=(p[i]-p[h])*(p[i-]-p[h])/;s=fabs(s);
printf("%.4LF",s/S);
return ;
}