【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

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;

}

小凸