【BZOJ4445】[Scoi2015]小凸想跑步
Description
小凸晚上喜欢到操场跑步,今天他跑完两圈之后,他玩起了这样一个游戏。
操场是个凸n边形,N个顶点按照逆时针从0~n-l编号。现在小凸随机站在操场中的某个位置,标记为P点。将P点与n个顶点各连一条边,形成N个三角形。如果这时P点,0号点,1号点形成的三角形的面积是N个三角形中最小的一个,小凸则认为这是一次正确站位。
现在小凸想知道他一次站位正确的概率是多少。
Input
第1行包含1个整数n,表示操场的顶点数和游戏的次数。
接下来有N行,每行包含2个整数Xi,Yi表示顶点的坐标。
输入保证按逆时针顺序输入点,所有点保证构成一个n多边形。所有点保证不存在三点共线。
Output
输出1个数,正确站位的概率,保留4位小数。
Sample Input
5
1 8
0 7
0 0
8 0
8 8
1 8
0 7
0 0
8 0
8 8
Sample Output
0.6316
HINT
3<=N<=10^5,-10^9<=X,Y<=10^9
题解:现在才发现,我有时喜欢用一条直线的左边来代表一个半平面,有时喜欢用一条直线的右面代表一个半平面。。不过无所谓啦~
题中的限制是三角形面积的大小关系,如果我们将三角形面积用叉积来表示的话很容易将所给条件变成n-1个不等式,外加n个不等式限定P在多边形内部。求半平面交即可。
至于精度。。。用long double,把eps删掉即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=200010;
typedef long double db;
struct point
{
db x,y;
point() {}
point(db a,db b) {x=a,y=b;}
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 db &a) const {return point(x*a,y*a);}
db operator * (const point &a) const {return x*a.y-y*a.x;}
}p[maxn];
struct line
{
point p,v;
db a;
line() {}
line(point x,point y) {p=x,v=y,a=atan2(v.y,v.x);}
}l[maxn];
int n,tot,h,t;
db ans,sum;
int q[maxn];
inline bool onlft(line a,point b)
{
return a.v*(b-a.p)>=0;
}
inline point getp(line a,line b)
{
point u=a.p-b.p;
db tmp=(b.v*u)/(a.v*b.v);
return a.p+a.v*tmp;
}
inline bool cmp(const line &a,const line &b)
{
if(fabs(a.a-b.a)==0) return onlft(a,b.p);
return a.a<b.a;
}
inline void HPI()
{
sort(l+1,l+tot+1,cmp);
int i,j=1;
for(i=2;i<=tot;i++) if(fabs(l[i].a-l[j].a)>0) l[++j]=l[i];
tot=j;
h=1,t=2,q[1]=1,q[2]=2;
for(i=3;i<=tot;i++)
{
while(h<t&&onlft(l[i],getp(l[q[t-1]],l[q[t]]))) t--;
while(h<t&&onlft(l[i],getp(l[q[h+1]],l[q[h]]))) h++;
q[++t]=i;
}
while(h<t&&onlft(l[q[h]],getp(l[q[t-1]],l[q[t]]))) t--;
for(i=h;i<t;i++) p[i]=getp(l[q[i]],l[q[i+1]]);
p[t]=getp(l[q[t]],l[q[h]]);
for(i=h;i<t;i++) ans+=p[i]*(p[i+1]-p[i]);
ans+=p[t]*(p[h]-p[t]);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd();
int i;
for(i=0;i<n;i++) p[i].x=rd(),p[i].y=rd();
p[n]=p[0];
for(i=0;i<n;i++) l[++tot]=line(p[i+1],p[i]-p[i+1]),sum+=p[i]*(p[i+1]-p[i]);
for(i=1;i<n;i++)
{
db a=p[i+1].x-p[i].x-p[1].x+p[0].x;
db b=p[i+1].y-p[i].y-p[1].y+p[0].y;
db c=-(p[i]*(p[i+1]-p[i]))+(p[0]*(p[1]-p[0]));
if(fabs(a)>0) l[++tot]=line(point(0,c/a),point(-a,-b));
else if(fabs(b)>0) l[++tot]=line(point(-c/b,0),point(0,-b));
}
HPI();
printf("%.4lf",(double)fabs(ans/sum));
return 0;
}