[SCOI2015]小凸想跑步

题目描述

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

操场是个凸 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 ;

}

巴特西

[SCOI2015]小凸想跑步

最新文章

热门文章