P4250 [SCOI2015] 小凸想跑步

K_srh · 2024-02-03 01:52:05 · 题解

题目大意：小凸晚上喜欢到操场跑步，今天他跑完两圈之后，他玩起了这样一个游戏。

操场是个凸 n 边形，n 个顶点按照逆时针从 0 \sim n-1 编号。

现在小凸随机站在操场中的某个位置，标记为 p 点。将 p 点与 n 个顶点各连一条边，形成 n 个三角形。如果这时 p 点，0 号点，1 号点形成的三角形的面积是 n 个三角形中最小的一个，小凸则认为这是一次正确站位。现在小凸想知道他一次站位正确的概率是多少。

转化：求符合条件的区域面积占总面积的比

思路：一眼看过去，这和标签里的半平面交有啥关系啊，别着急，先推下柿子！

设第 i 个顶点的坐标为 A_i(x_i,y_i)，可以用向量的叉乘表示下面积

因为 S_{\triangle A_1A_0P} < S_{\triangle A_{i+1}A_iP}（i 从 1 到 n-1）

所以有 \overrightarrow{A_0A_1} \times \overrightarrow{A_0P} < \overrightarrow{A_iA_{i+1}} \times \overrightarrow{A_iP}

设点 P(x,y)

我们将叉乘展开,即

将等式左边移到右边即为

对于所有 1\leq i \leq n-1 成立（当 i=n-1 时，i+1 用 0 替代）

这东西怎么这么眼熟，这不就是半平面交的解析式嘛！！！

把半平面的解析表达式转换成“向量左半平面”的表示形式，然后求半平面交即可。

另外还要记得 P(x,y) 必须在凸多边形内部，所以凸多边形的边也要加进来一起做半平面交。

对于 Ax+By+C>0 这里给出一种不会爆出 0 导致奇怪错误的加线方式

（p 是源点，v 是方向向量，line 是线的结构体数组）

接下来就是欢乐的代码环节啦！！！

#include<bits/stdc++.h>
#define debug(x) cerr<<__LINE__<<" : "<<#x<<"="<<(x)<<endl 
#define int long long
using namespace std;
const double eps=1e-12; 
const int N=3e5+5;
struct point{
    double x,y;
    point(double x=0,double y=0):x(x),y(y){};
    double lenght()
    {
        return sqrt(x*x+y*y);
    }
};
point operator * (const double &a, const point &b){
    return point(a*b.x, a*b.y);
}
int dcmp(double x)
{
    if(fabs(x)<eps)return 0;
    if(x<0)return -1;
    return 1;
}
point operator-(const point &a,const point &b)
{
    return point(a.x-b.x,a.y-b.y);
}
point operator+(const point &a,const point &b)
{
    return point(a.x+b.x,a.y+b.y);
}
bool operator<(const point &a,const point &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double cross(point a,point b)
{
    return a.x*b.y-a.y*b.x;
}
double dot(point a,point b)
{
    return a.x*b.x+a.y*b.y;
}
struct Line{
    point A,v;
    double pol;
    Line(){};
    Line(const point &A,const point &v):A(A),v(v),pol(atan2(v.y,v.x)){};
    bool notleft(const point &B)const
    {
        return dcmp(cross(v,B-A))<=0;
    }
};
bool operator < (const Line &l,const Line &r)
{
    return dcmp(l.pol-r.pol)<0||(dcmp(l.pol-r.pol)==0&&dcmp(cross(l.v,r.A-l.A)<0));

}
point LineIns(const Line &l,const Line &r)
{
    double a1=cross(r.v,l.A-r.A);
    double a2=cross(r.v,l.A+l.v-r.A);
    double lam=a1/(a1-a2);
    return l.A+(lam*l.v);
}
int halfplane(Line l[],int n,Line hp[],point ins[])
{
    sort(l+1,l+1+n);
    int tot=0;
    for(int i=1;i<=n;i++)
    {
        if(tot&&dcmp(l[i].pol-l[tot].pol)==0)continue;
        l[++tot]=l[i];
    }
    int pl=1,pr=0;
    for(int i=1;i<=tot;i++)
    {
        while(pr-pl>=1&&l[i].notleft(ins[pr]))pr--;
        while(pr-pl>=1&&l[i].notleft(ins[pl+1]))pl++;       
        hp[++pr]=l[i];
        if(pr-pl>=1)ins[pr]=LineIns(hp[pr],hp[pr-1]);
    }
    while(pr-pl>=1&&hp[pl].notleft(ins[pr]))pr--;
    if(pr-pl>=2)ins[pl]=LineIns(hp[pl],hp[pr]);
    for(int i=pl;i<=pr;i++)
    {
        hp[i-pl+1]=hp[i];
        ins[i-pl+1]=ins[i];
    }
    return pr-pl+1;
}
double getarea(point p[],int n)
{
    double area=0;
    for(int i=2;i<=n-1;i++)
    {
        area+=cross(p[i]-p[1],p[i+1]-p[1]);
    }
    return area/2;
}
Line line[N],hp[N];
point p[N],ins[N],lp[N],pp[N]; 
signed main()
{
    int n,tot=0,cnt;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
    for(int i=1;i<=n;i++)
    {
        line[++tot]=Line(p[i],p[i%n+1]-p[i]);
    }
    double sum=getarea(p,n);
    for(int i=0;i<=n-1;i++)pp[i]=p[i+1];
    for(int i=1;i<=n-1;i++)
    {
        double A=pp[1].y-pp[0].y-pp[(i+1)%n].y+pp[i].y;
        double B=pp[0].x-pp[1].x+pp[(i+1)%n].x-pp[i].x;
        double C=pp[i].x*pp[(i+1)%n].y-pp[(i+1)%n].x*pp[i].y-pp[0].x*pp[1].y+pp[1].x*pp[0].y;
        line[++tot]=Line({-C/(A*A+B*B)*A,-C/(A*A+B*B)*B},{B,-A});
    }
    cnt=halfplane(line,tot,hp,ins);
    double pml=getarea(ins,cnt);
    printf("%.4lf",pml/sum);
    return 0;
}