NKOJ 2003 （CQOI 2006）凸多边形（半平面交）

发表于 |
字数统计: 653字 | 阅读时长 ≈ 3min

P2003【CQOI2006】凸多边形

问题描述

逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图：
这里写图片描述
则相交部分的面积为5.233。

输入格式

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

输出格式

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

样例输入

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

样例输出

5.233

提示

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

向量表示直线，做暴力半平面交，复杂度$O(n^2)$，保存模板。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 2005
using namespace std;
const double eps=1e-9;
struct node
{
	double  x,y;
	double operator*(const node &b)const
	{return x*b.y-y*b.x;}
	node operator+(const node &b)const 
	{return (node){x+b.x,y+b.y};}
	node operator-(const node &b)const
	{return (node){x-b.x,y-b.y};}
	node operator*(const double b)const
	{return (node){b*x,b*y};}
}A[15][N],S[N],T[N];
struct nodd{node p,v;}Line[N];
int n,m,top;
node Intersection(nodd a,nodd b)
{
	double k=((a.p-b.p)*a.v)/(b.v*a.v);
	return b.p+b.v*k;
}
void Cut(nodd D)
{
	int i,j,k=0;
	S[0]=S[top];
	S[top+1]=S[1];
	for(i=1;i<=top;i++)
	{
		if(D.v*(S[i]-D.p)<-eps)
		{
			if(D.v*(S[i-1]-D.p)>-eps)T[++k]=Intersection(D,nodd{S[i-1],S[i]-S[i-1]});
			if(D.v*(S[i+1]-D.p)>-eps)T[++k]=Intersection(D,nodd{S[i],S[i+1]-S[i]});
		}
		else T[++k]=S[i];
	}
	copy(T+1,T+k+1,S+1);top=k;
}
double Garea()
{
	int i,j,k=0;
	S[top+1]=S[1];
	double ans=0;
	for(i=1;i<=top;i++)ans+=S[i]*S[i+1];
	return ans;
}
int main()
{
	int i,j,k;double x,y,z;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&k);
		for(j=1;j<=k;j++)scanf("%lf%lf",&A[i][j].x,&A[i][j].y);
		for(j=1;j<=k;j++)Line[++m]=(nodd){A[i][j],A[i][j%k+1]-A[i][j]};
	}
	S[++top]=(node){-1e5,1e5};
	S[++top]=(node){-1e5,-1e5};
	S[++top]=(node){1e5,-1e5};
	S[++top]=(node){1e5,1e5};
	for(i=1;i<=m;i++)Cut(Line[i]);
	printf("%.3lf",0.5*Garea());
}