bzoj 4445: [Scoi2015]小凸想跑步

.

题意：在一个凸多边形中随机选一个点，问有多大概率使得这个点与第一条边构成的三角形是所构成的n个三角形中最小的。
题解：半平面交。
很明显，所有答案都集中在一块地方，所以只要分别求出只存在第一条边和其他每条边的限制，跑半平面交就好了。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,num=0,nn=0,q[200010];
struct pnt
{
    double x,y;
}ansp[200010],p[100010];
struct line
{
    pnt x,y;
    double angle;
}a[200010];
const double eps=1e-14;
double ans=0;

void out(line x)
{
    printf("%g %g %g %g %g\n",x.x.x,x.x.y,x.y.x,x.y.y,x.angle);
}
double dis(pnt x,pnt y)
{
    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
void add(double x1,double y1,double x2,double y2)
{
    num++;
    a[num].x={x1,y1};
    a[num].y={x2,y2};
    a[num].angle=atan2(y2-y1,x2-x1);
}
double multi(pnt p0,pnt p1,pnt p2)
{
    double x1=p1.x-p0.x,y1=p1.y-p0.y,x2=p2.x-p0.x,y2=p2.y-p0.y;
    return x1*y2-x2*y1;
}
int cmp(line x,line y)
{
    if(abs(x.angle-y.angle)<eps)
    return multi(x.x,x.y,y.x)<0;
    return x.angle<y.angle;
}
pnt jd(line x,line y)
{
    double s1=multi(x.x,x.y,y.x),s2=multi(x.x,y.y,x.y);
    pnt ans;
    ans.x=(y.x.x*s2+y.y.x*s1)/(s1+s2);
    ans.y=(y.x.y*s2+y.y.y*s1)/(s1+s2);
    return ans;
}
bool chk(line l0,line l1,line l2)
{
    pnt hh=jd(l1,l2);/*
    out(l0);
    out(l1);
    out(l2);*/
//    printf("%g %g\n\n",hh.x,hh.y);
    return multi(l0.x,l0.y,hh)<-eps;
}
void wk()
{
    sort(a+1,a+1+num,cmp);
    a[0].angle=-1e10;
    for(int i=1;i<=num;i++)
    if(a[i].angle-a[i-1].angle>eps)
    a[nn++]=a[i];
    num=nn;/*
    for(int i=0;i<num;i++)
    printf("%g %g %g %g %g\n",a[i].x.x,a[i].x.y,a[i].y.x,a[i].y.y,a[i].angle);
    puts("");*/
    q[0]=0;
    q[1]=1;
    int st=0,ed=1;
    for(int i=2;i<num;i++)
    {
        while(st<ed&&chk(a[i],a[q[ed]],a[q[ed-1]]))ed--;
        while(st<ed&&chk(a[i],a[q[st]],a[q[st+1]]))st++;
        q[++ed]=i;
    }
    while(st<ed&&chk(a[q[st]],a[q[ed]],a[q[ed-1]]))ed--;
    while(st<ed&&chk(a[q[ed]],a[q[st]],a[q[st+1]]))st++;
    nn=0;/*
    for(int i=st;i<=ed;i++)
    printf("%d ",q[i]);
    puts("");*/
    q[++ed]=q[st];
    for(int i=st;i<ed;i++)
    ansp[++nn]=jd(a[q[i]],a[q[i+1]]);
}
line get(int x,double y)
{
    line ans;
    double len=dis(a[x].x,a[x].y);
    ans.x.x=a[x].x.x-y/len*(a[x].y.y-a[x].x.y);
    ans.x.y=a[x].x.y+y/len*(a[x].y.x-a[x].x.x);
    ans.y.x=a[x].y.x-y/len*(a[x].y.y-a[x].x.y);
    ans.y.y=a[x].y.y+y/len*(a[x].y.x-a[x].x.x);
    return ans;
}
void ins(double a,double b,double c)//ax+by<=c
{
//    printf("%lfx+%lfy<=%lf\n",a,b,c);
    if(abs(b)<eps)
    {
        pnt p1={c/a,0},p2={c/a,1};
        if(a>eps)
        add(p1.x,p1.y,p2.x,p2.y);
        else
        add(p2.x,p2.y,p1.x,p1.y);
        return;
    }
    pnt p1={0,c/b},p2={1,(c-a)/b};
    if(b>eps)
    {
        add(p2.x,p2.y,p1.x,p1.y);
    }
    else
    {
        add(p1.x,p1.y,p2.x,p2.y);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%lf%lf",&p[i].x,&p[i].y);
    p[n]=p[0];
    for(int i=1;i<=n;i++)
    add(p[i-1].x,p[i-1].y,p[i].x,p[i].y);
    for(int i=2;i<=n;i++)
    {
        line x=a[1],y=a[i];
        ins(x.x.y-x.y.y+y.y.y-y.x.y,
            x.y.x-x.x.x+y.x.x-y.y.x,
            x.x.y*(x.y.x-x.x.x)-x.x.x*(x.y.y-x.x.y)-y.x.y*(y.y.x-y.x.x)+y.x.x*(y.y.y-y.x.y));
    }/*
    for(int i=1;i<=num;i++)
    out(a[i]);*/
    wk();
    ansp[0]=ansp[nn];
    for(int i=0;i<nn;i++)
    ans+=ansp[i].x*ansp[i+1].y-ansp[i+1].x*ansp[i].y;
    double s=0;
    for(int i=0;i<n;i++)
    s+=p[i].x*p[i+1].y-p[i+1].x*p[i].y;
    char ss[10];
    sprintf(ss,"%.6lf",ans/s);
    if(ss[6]>='5')
    {
        ss[5]++;
        if(ss[5]>'9')
        {
            ss[5]='0';
            ss[4]++;
        }
        if(ss[4]>'9')
        {
            ss[4]='0';
            ss[3]++;
        }
        if(ss[3]>'9')
        {
            ss[3]='0';
            ss[2]++;
        }
        if(ss[2]>'9')
        {
            ss[2]='0';
            ss[0]++;
        }
    }
    for(int i=0;i<6;i++)
    printf("%c",ss[i]);
}