题目描述
小凸晚上喜欢到操场跑步，今天他跑完两圈之后，他玩起了这样一个游戏。
操场是个凸 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-15; int n,top,tot; double x[N],y[N],s,S; inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } struct point{ double x,y; point(double xx=0,double yy=0){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=0,double x2=0,double x3=0,double x4=0){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=0;i<n;++i){ x[i]=rd(),y[i]=rd(); if(i)l[++top]=line(x[i-1],y[i-1],x[i],y[i]); } l[++top]=line(x[n-1],y[n-1],x[0],y[0]); for(int i=2;i<n;++i)S+=(point(x[i],y[i])-point(x[0],y[0]))*(point{x[i-1],y[i-1]}-point{x[0],y[0]})/2;S=fabs(S); x[n]=x[0];y[n]=y[0]; for(int i=1;i<n;++i){ double a=-y[1]+y[0]+y[i+1]-y[i],b=-x[0]+x[1]+x[i]-x[i+1],c=x[0]*y[1]-x[1]*y[0]-x[i]*y[i+1]+x[i+1]*y[i]; if(fabs(b)<eps){ if(fabs(a)<eps){puts("0.0000");return 0;} double xf=-c/a,xs=xf,yf=0,ys=1e15; if(a<0)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>=0){l[++top]=line(xs,ys,xf,yf); }else l[++top]=line(xf,yf,xs,ys); } } for(int i=1;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+1,l+top+1); for(int i=1;i<=top;++i)if(i==1||fabs(l[i].ang-l[i-1].ang)>eps)a[++tot]=l[i]; int h=1,t=2;q[1]=a[1];q[2]=a[2];p[1]=jiao(a[1],a[2]); for(int i=3;i<=tot;++i){ while(h<t&&left(p[t-1],a[i]))t--; while(h<t&&left(p[h],a[i]))h++; q[++t]=a[i];p[t-1]=jiao(q[t-1],q[t]); } while(h<t&&left(p[h],q[t]))h++; while(h<t&&left(p[t-1],q[h]))t--; p[t]=jiao(q[t],q[h]); for(int i=h+2;i<=t;++i)s+=(p[i]-p[h])*(p[i-1]-p[h])/2;s=fabs(s); printf("%.4LF",s/S); return 0; }