#2008. 「SCOI2015」小凸想跑步

题目描述

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

操场是个凸 n nn 边形，N NN 个顶点按照逆时针从 0∼n−1 0 \sim n - 10∼n−1 编号。现在小凸随机站在操场中的某个位置，标记为 P PP 点。将 P PP 点与 n nn 个顶点各连一条边，形成 N NN 个三角形。如果这时 P PP 点，0 00 号点，1 11 号点形成的三角形的面积是 N NN 个三角形中最小的一个，小凸则认为这是一次正确站位。

现在小凸想知道他一次站位正确的概率是多少。

输入格式

第一行包含 1 11 个整数 n nn，表示操场的顶点数和游戏的次数。
接下来有 N NN 行，每行包含两个整数 Xi X_iXi、Yi Y_iYi 表示顶点的坐标。
输入保证按逆时针顺序输入点，所有点保证构成一个 n nn 多边形。所有点保证不存在三点共线。

输出格式

输出一个数，正确站位的概率，保留 4 44 位小数。

样例

样例输入

样例输出

0.6316

数据范围与提示

3≤N≤105,−109≤X,Y≤109 3 \leq N \leq 10 ^ 5, -10 ^ 9 \leq X, Y \leq 10 ^ 93≤N≤105,−109≤X,Y≤109

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 100010

#define eps 0.001

using namespace std;

struct node{

    double x,y;

    node(double a=,double b=):x(a),y(b){}

    node operator + (const node &c)

    {return node(x+c.x,y+c.y);}

    node operator - (const node &c)

    {return node(x-c.x,y-c.y);}

    double operator * (const node &c)

    {return x*c.y-y*c.x;}

    node operator / (const double c)

    {return node(x/c,y/c);}

}p[maxn];

int n;

double cnt1,cnt2,S;

double abs(double x){return x>?x:-x;}

void check(double x,double y){

    node point=node(x,y);

    double mn=;int k=-;double sum=;

    for(int i=;i<n;i++){

        node a=p[i],b=p[(i+)%n];

        double s=(a-point)*(b-point)*0.5;

        s=abs(s);

        if(s<mn)mn=s,k=i;

        sum+=s;

    }

    if(abs(sum-S)<=eps){

        cnt1+=;

        if(k==)cnt2+=;

    }

}

int main(){

    scanf("%d",&n);

    double mxx=,mnx=,mxy=,mny=;

    for(int i=;i<n;i++){

        scanf("%lf%lf",&p[i].x,&p[i].y);

        mxx=max(mxx,p[i].x);

        mxy=max(mxy,p[i].y);

        mnx=min(mnx,p[i].x);

        mny=min(mny,p[i].y);

    }

    for(int i=;i<n;i++)

        S+=(p[i]-p[])*(p[i+]-p[]);

    S*=0.5;

    S=abs(S);

    for(double i=mnx;i<=mxx;i+=0.001)

        for(double j=mny;j<=mxy;j+=0.001)

            check(i,j);

    cnt2+=(n-)*;cnt1+=(n-)*;

    cnt2/=cnt1;

    printf("%.4lf",cnt2);

    return ;

}

20分乱搞

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define maxn 200010

using namespace std;

struct node{

    long double x,y;

    node(){}

    node(long double a,long double b){x=a,y=b;}

    node operator + (const node &a)

    {return node(x+a.x,y+a.y);}

    node operator - (const node &a)

    {return node(x-a.x,y-a.y);}

    node operator * (const long double &a)

    {return node(x*a,y*a);}

    long double operator * (const node &a)

    {return x*a.y-y*a.x;}

}p[maxn];

struct line{

    node p,v;

    long double a;

    line(){}

    line(node x,node y){p=x,v=y,a=atan2(v.y,v.x);}

}l[maxn];

int n,tot,h,t,q[maxn];

long double ans,sum;

bool onleft(line a,node b){

    return a.v*(b-a.p)>=;

}

node getp(line a,line b){

    node u=a.p-b.p;

    long double tmp=(b.v*u)/(a.v*b.v);

    return a.p+a.v*tmp;

}

bool cmp(line a,line b){

    if(fabs(a.a-b.a)==)return onleft(a,b.p);

    return a.a<b.a;

}

inline void work(){

    sort(l+,l+tot+,cmp);

    int j=;

    for(int i=;i<=tot;i++)  if(fabs(l[i].a-l[j].a)>)    l[++j]=l[i];

    tot=j;

    h=,t=,q[]=,q[]=;

    for(int i=;i<=tot;i++){

        while(h<t&&onleft(l[i],getp(l[q[t-]],l[q[t]])))t--;

        while(h<t&&onleft(l[i],getp(l[q[h+]],l[q[h]])))h++;

        q[++t]=i;

    }

    while(h<t&&onleft(l[q[h]],getp(l[q[t-]],l[q[t]])))t--;

    for(int i=h;i<t;i++) p[i]=getp(l[q[i]],l[q[i+]]);

    p[t]=getp(l[q[t]],l[q[h]]);

    for(int i=h;i<t;i++)ans+=p[i]*(p[i+]-p[i]);

    ans+=p[t]*(p[h]-p[t]);

}

int main(){

    freopen("Cola.txt","r",stdin);

    scanf("%d",&n);

    for(int i=;i<n;i++)cin>>p[i].x>>p[i].y;

    p[n]=p[];

    for(int i=;i<n;i++){

        l[++tot]=line(p[i+],p[i]-p[i+]);

        sum+=p[i]*(p[i+]-p[i]);

    }

    for(int i=;i<n;i++){

        long double a=p[i+].x-p[i].x-p[].x+p[].x;

        long double b=p[i+].y-p[i].y-p[].y+p[].y;

        long double c=-(p[i]*(p[i+]-p[i]))+(p[]*(p[]-p[]));

        if(fabs(a)>)l[++tot]=line(node(,c/a),node(-a,-b));

        else if(fabs(b)>)l[++tot]=line(node(-c/b,),node(,-b));

    }

    work();

    printf("%.4lf",(double)fabs(ans/sum));

    return ;

}

100分半平面交

巴特西

loj #2008. 「SCOI2015」小凸想跑步