好久没有做计算几何的题了,先复习一下。

叉积在这里的意义就是表示沿直线方向(由起点到终点)的两条直线进行比较以及求面积。

有$\alpha,\beta$,若$\alpha\times \beta<0$,则$\alpha$在$\beta$左侧,$\beta$在$\alpha$右侧

反之亦然。

面积是平行四边形的面积,实际问题要除以$2$。

以前的SI模板有点臃肿,所以需要学习借鉴别人。

求交点的公式:($p_1,p_3$为两起点,其他同理)

$p=p_1+\frac{(p_2-p_1)*mul(p_1-p_3,p_4-p_3)}{mul(p4-p_3,p_2-p_1)}$

$y$同理。

其他部分均可理解。

进入正题,

这道题就是$P(x,y)$在有限范围内,达成限制条件的概率。

把不等式一列,

$(x_1-x_0)(y-y_0)-(x-x_0)(y_1-y_0)\le (x_i-x_{i-1})(y-y_{i-1})-(x-x_{i-1})(y_i-y_{i-1})$

$$(x_1-x_0-(x_i-x_{i-1}))y-(y_1-y_0-(y_i-y_{i-1}))x+(x_0y_1-x_1y_0-(x_{i-1}y_i-x_iy_{i-1}))\le 0$$

转化成半平面交模板。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-7
using namespace std;
const int N=2e5+5;
struct point 
{
    double x,y;
    point(double x=0.0,double y=0.0):x(x),y(y){}
    double angle(){return atan2(y,x);}
    point operator +(const point a)const{return point(x+a.x,y+a.y);}
    point operator -(const point a)const{return point(x-a.x,y-a.y);}
    point operator *(const double a)const{return point(x*a,y*a);}
}p[N],q1[N];
struct line
{
    point s,t;double ang;
    line(){};
    line(point S,point T){s=S,t=T;ang=(T-S).angle();}
}e[N],q2[N];int l,r,n,m;
inline double mul(point a,point b){return a.x*b.y-b.x*a.y;}
inline bool isr(line a,point b){return mul(b-a.s,a.t-a.s)>0;}
inline bool cmp(line a,line b){return fabs(a.ang-b.ang)<eps?isr(a,b.t):a.ang<b.ang;}
inline point jd(line a,line b){return a.s+(a.t-a.s)*(mul(a.s-b.s,b.t-b.s)/mul(b.t-b.s,a.t-a.s));}
void SI()
{
    sort(e+1,e+m+1,cmp);
    q2[l=r=1]=e[1];
    for(int i=2;i<=m;i++)
        if(fabs(e[i].ang-e[i-1].ang)>eps)
        {
            while(l<r&&isr(e[i],q1[r-1]))--r;
            while(l<=r&&isr(e[i],q1[l]))++l;
            q1[r]=jd(q2[r],e[i]);
            q2[++r]=e[i];
        }
    while(l<r&&isr(q2[l],q1[r-1]))--r;
    q1[r]=jd(q2[l],q2[r]);
}
double area()
{
    if(r-l<2)return 0;
    double ans=0;
    for(int i=l;i<r;i++)ans+=mul(q1[i],q1[i+1]);
    ans+=mul(q1[r],q1[l]);
    return ans/2;
}
int main()
{
    scanf("%d",&n);m=n;double sum=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        e[i]=line(p[i-1],p[i]);
        if(i!=1)sum+=mul(p[i-1],p[i]);
    }
    e[1]=line(p[n],p[1]);
    sum+=mul(p[n],p[1]);
    sum/=2;
    p[++n]=p[1];
    for(int i=3;i<=n;i++)
    {
        double A=p[1].y-p[2].y-(p[i-1].y-p[i].y);
        double B=p[2].x-p[1].x-(p[i].x-p[i-1].x);
        double C=mul(p[1],p[2])-mul(p[i-1],p[i]);
        if(fabs(A)<eps)e[++m]=line(point(0,-C/B),point(0,-C/B)+point(-B,A));
        else e[++m]=line(point(-C/A,0),point(-C/A,0)+point(-B,A));
    }
    SI();
    printf("%.4lf\n",area()/sum);
    return 0;
}