BZOJ4445: [Scoi2015]小凸想跑步

裸半平面交。记得把P0P1表示的半平面加进去，否则点可能在多边形外。

#include<algorithm>

#include<cstdio>

#include<cmath>

using std::sort;

typedef double flo;

const int N=1e5+5;

struct vec{flo x,y;}p[N],q2[N];

flo det(vec a,vec b){return a.x*b.y-a.y*b.x;}

vec operator+(vec a,vec b){return(vec){a.x+b.x,a.y+b.y};}

vec operator-(vec a,vec b){return(vec){a.x-b.x,a.y-b.y};}

vec operator*(flo a,vec b){return(vec){a*b.x,a*b.y};}

struct line{

	vec p,v;

	flo a;

	void cal(){a=atan2(v.y,v.x);}

}r[N],q1[N];

flo cal(vec a,line b){return det(a-b.p,b.v);}

bool operator<(line a,line b){return a.a<b.a||a.a==b.a&&cal(a.p,b)<0;}

vec over(line a,line b){

	return a.p+det(a.p-b.p,b.v)/det(b.v,a.v)*a.v;

}

void ins(int i,int j){

	flo a=p[0].y-p[i].y-p[1].y+p[j].y;

	flo b=p[1].x-p[j].x-p[0].x+p[i].x;

	flo c=det(p[0],p[1])-det(p[i],p[j]);

	r[i].p.x=b?0:-c/a;

	r[i].p.y=b?-c/b:0;

	r[i].v=(vec){-b,a};

}

flo area(vec*p,int n){

	flo s=det(p[n-1],p[0]);

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

		s+=det(p[i-1],p[i]);

	return s;

}

int main(){

	struct{

		operator int(){

			int x=0,y=0,c=getchar();

			while(c<48)

				y=c==45,c=getchar();

			while(c>47)

				x=x*10+c-48,c=getchar();

			return y?-x:x;

		}

	}it;

	int n=it;

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

		p[i].x=it,p[i].y=it;

	r[0].p=p[0];

	r[0].v=p[1]-p[0];

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

		ins(i,(i+1)%n);

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

		r[i].cal();

	sort(r,r+n);

	int a=0,b=-1;

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

		while(a<b&&cal(q2[b],r[i])>0)--b;

		while(a<b&&cal(q2[a+1],r[i])>0)++a;

		if(a>b||r[i].a!=q1[b].a)

			q1[++b]=r[i],q2[b]=over(q1[b],q1[b-1]);

	}

	while(a<b&&cal(q2[b],q1[a])>0)--b;

	q2[a]=over(q1[a],q1[b]);

	flo s=area(q2+a,b-a+1)/area(p,n);

	printf("%.4f\n",s);

}