bzoj 2618: [Cqoi2006]凸多边形 — 半平面交

2618: [Cqoi2006]凸多边形

Time Limit: 5 Sec  Memory Limit: 128 MB

Description

逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图：

则相交部分的面积为5.233。

Input

第一行有一个整数n，表示凸多边形的个数，以下依次描述各个多边形。第i个多边形的第一行包含一个整数m_i，表示多边形的边数，以下m_i行每行两个整数，逆时针给出各个顶点的坐标。

Output

输出文件仅包含一个实数，表示相交部分的面积，保留三位小数。

Sample Input

2
6
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
4
0 -3
1 -1
2 2
-1 0

Sample Output

5.233

HINT

100%的数据满足：2<=n<=10，3<=m_i<=50，每维坐标为[-1000,1000]内的整数

Source

就是暴力的求半平面交就好了

人家让保留三位小数我puts(“0.00”)调了半天qwq

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 1010
#define db double
inline int rd()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct mp{db x,y;}a[N],g[N];
mp operator +(mp a,mp b){return (mp){a.x+b.x,a.y+b.y};}
mp operator -(mp a,mp b){return (mp){a.x-b.x,a.y-b.y};}
db operator *(mp a,mp b){return a.x*b.y-a.y*b.x;}
mp operator *(db a,mp b){return (mp){b.x*a,b.y*a};}
struct xx{mp x,y;db af;}c[N],f[N];
bool operator <(xx a,xx b){return a.af==b.af?a.y*(b.x-a.x)<0:a.af<b.af;}
int n,m,tot;
bool fl=0;
mp Q(xx a,xx b)
{
	db t=a.y*b.y;
	if(!t) fl=1;
	return (b.y*(a.x-b.x))/t*a.y+a.x;
}
int main()
{
	n=rd();
	for(int i=1;i<=n;i++)
	{
		m=rd();
		for(int j=1;j<=m;j++) a[j].x=rd(),a[j].y=rd();
		a[m+1]=a[1];
		for(int j=1;j<=m;j++) c[++tot]=(xx){a[j],a[j+1]-a[j],atan2(a[j+1].y-a[j].y,a[j+1].x-a[j].x)};
	}
	sort(c+1,c+tot+1);
	int l=1,r=0;
	for(int i=1;i<=tot;i++)
	{
		if(i==1||c[i].af>c[i-1].af)
		{
			xx x=c[i];
			while(l<r&&x.y*(g[r]-x.x)<=0) r--;
			while(l<r&&x.y*(g[l+1]-x.x)<=0) l++;
			f[++r]=x;
			if(l<r) g[r]=Q(f[r-1],x);
			if(fl){puts("0.000");return 0;}
		}
	}
	while(l<r&&f[l].y*(g[r]-f[l].x)<=0) r--;
	while(l<r&&f[r].y*(g[l+1]-f[r].x)<=0) l++;
	g[l]=g[r+1]=Q(f[l],f[r]);
	if(fl){puts("0.000");return 0;}
	db ans=0;
	for(int i=l;i<=r;i++) ans+=g[i]*g[i+1];
	printf("%.3lf\n",fabs(ans)/2);
	return 0;
}