欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

luogu P4196

程序员文章站 2022-06-02 21:26:18
...

题目链接

题意

给一些多边形,求这些多边形的面积并

数据范围

每个多边形至多50条边,至多有10个多边形

解法

半平面交
这里介绍的是O(nlogn)O(nlogn)的做法:
首先考虑如何比较优秀的直线求交,这个是接下来算法步骤的灵魂问题
考虑使用面积法:
luogu P4196
如图,可以看到三角形p1p2v1和四边形p1p2v1v2同底,所以它们的面积比就是高之比,又由于相似,它们的高之比可以看成线段(p2-交点)和(p2-v2)的长度之比。所以求出这个之后加上p2就可以得到交点的坐标了。

然后考虑半平面交问题,这里我们规定所有线段都是左边为有效区间,然后将所有线段一起按照极角排序,相同极角的靠左边的放在后面,然后用双端队列维护半平面交,计算的时候就是考虑一条线段加进去后,会不会影响之前的半平面交。又了直线求交的方法后就比较简单了,具体可以看代码。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
const double eps=1e-7;
struct node{
	double x,y;
	node (double xx=0,double yy=0){x=xx,y=yy;}
}b[maxn];
double operator ^(node a,node b){return a.x*b.y-a.y*b.x;}
node operator +(node a,node b){return node(a.x+b.x,a.y+b.y);}
node operator -(node a,node b){return node(a.x-b.x,a.y-b.y);}
node operator *(double a,node b){return node(a*b.x,a*b.y);}
struct line{
	node v,p;
	double poa;
}a[maxn],q[maxn];
int n,js;
inline int sign(double a){
	if(fabs(a)<=eps)return 0;
	return a>0?1:-1;
}
bool cmp(line a,line b){
	if(sign(a.poa-b.poa))return sign(a.poa-b.poa)<0;
	else return sign((a.v-a.p)^(b.v-a.p))>0;
}
node inter(line a,line b){
	node p1=a.p,v1=a.v,p2=b.p,v2=b.v;
	v1=v1-p1,v2=v2-p2;
	node alfa=p2-p1;
	node tmp=p2+((alfa^v1)/(v1^v2))*v2;
	return tmp;
}
int cnt=0;
inline bool pd(line a,line b,line c){
	node p=inter(a,b);
	return sign((c.v-c.p)^(p-c.p))<0;
}
void bpm(){
	sort(a+1,a+1+js,cmp);
	for(int i=1;i<=js;i++){
		if(sign(a[i].poa-a[i-1].poa)!=0)cnt++;//极角不同才保留
		a[cnt]=a[i];
	}
	int h=1,t=0;
	q[++t]=a[1],q[++t]=a[2];
	for(int i=3;i<=cnt;i++){
		while(h<t&&pd(q[t-1],q[t],a[i]))t--;
		while(h<t&&pd(q[h+1],q[h],a[i]))h++;
		q[++t]=a[i];
	}
	while(h<t&&pd(q[t-1],q[t],q[h]))t--;//注意最后要记得把头和尾判断一下
	while(h<t&&pd(q[h+1],q[h],q[t]))h++;
	q[t+1]=q[h];//这里容易忘记,因为是多边形,首尾相连
	js=0;
	for(int i=h;i<=t;i++){
		b[++js]=inter(q[i],q[i+1]);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int k;
		scanf("%d",&k);
		for(int j=1;j<=k;j++){
			scanf("%lf%lf",&b[j].x,&b[j].y);
		}
		b[k+1]=b[1];
		for(int j=1;j<=k;j++)a[++js].p=b[j],a[js].v=b[j+1];
	}
	for(int i=1;i<=js;i++)
	a[i].poa=atan2(a[i].v.y-a[i].p.y,a[i].v.x-a[i].p.x);
	bpm();
	b[js+1]=b[1];
	double ans=0;
	if(js>2)
	for(int i=1;i<=js;i++)ans+=b[i]^b[i+1];
	ans=fabs(ans)/2.0;
	printf("%.3lf\n",ans);
	return 0;
}