半平面交用于求几个凸包围成的面积

一条直线可以将平面分为两部分，我们取左半部分，右半部分舍弃，那么所有的直线围成的左半部分的面积的交集就是半平面交。

算法流程

首先把所有线首先按照角度从小到大排序，角度相同就按照线从左到右排序，排序后用一个双端队列来维护，每次新进来一条边，判断这条边是否在队列的队尾两条边的交点左边，如果是，就把队尾元素pop出去，如此往复，队头也是如此，所有边遍历完后还要用队头去维护队尾，用队尾去维护队头

线点

1
2
3
4
5
6
struct point{
	double x,y;
}pt[MAXN];
struct line{
	point a,b;
}L[MAXN];

函数

思想很简单，但是实现很复杂，一点点错误满盘皆输，这8个函数非常有用

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
point operator-(point a,point b){	//重载运算符 
	return {a.x-b.x,a.y-b.y};
}
double cross(point a,point b){		//叉积 
	return a.x*b.y-a.y*b.x;
}
double area(point a,point b,point c){	//ab向量叉乘ac向量 
	return cross(b-a,c-a);
}
double get_angle(line x){	//得到线的角度 
	return atan2(x.b.y-x.a.y,x.b.x-x.a.x);
}
bool cmp(line a,line b){
	double ag1=get_angle(a),ag2=get_angle(b);	//得到两条线的角度 
	if(ag1==ag2) return (area(a.a,a.b,b.b)<0);	//返回左边的，这是因为两条平行的直线左边的有用 
	else return ag1<ag2;	//角度小的在前 
}
point get_J(point p,point u,point q,point v){	//得到交点 
	point w=p-q;
	double t=cross(v,w)/cross(u,v);
	return {p.x+u.x*t,p.y+u.y*t};
}
point get_J(line a,line b){		//重载 
	return get_J(a.a,a.b-a.a,b.a,b.b-b.a); 
}
bool onRight(line a,line b,line c){		//判断a是否在bc交点右面 
	point x=get_J(b,c);
	return area(a.a,a.b,x)<=0; 
}

ACWING2803凸多边形

代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <cmath> 
#include <algorithm>
#include <iomanip>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const double pi=acos(-1);
const int SUP=0x800000;
const int MAXN=1e6+100;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
struct point{
	double x,y;
}pt[MAXN];
struct line{
	point a,b;
}L[MAXN];
int cnt,n,m;
int front,tail;
int dq[MAXN];
point operator-(point a,point b){	//重载运算符 
	return {a.x-b.x,a.y-b.y};
}
double cross(point a,point b){		//叉积 
	return a.x*b.y-a.y*b.x;
}
double area(point a,point b,point c){	//ab向量叉乘ac向量 
	return cross(b-a,c-a);
}
double get_angle(line x){	//得到线的角度 
	return atan2(x.b.y-x.a.y,x.b.x-x.a.x);
}
bool cmp(line a,line b){
	double ag1=get_angle(a),ag2=get_angle(b);	//得到两条线的角度 
	if(ag1==ag2) return (area(a.a,a.b,b.b)<0);	//返回左边的，这是因为两条平行的直线左边的有用 
	else return ag1<ag2;	//角度小的在前 
}
point get_J(point p,point u,point q,point v){	//得到交点 
	point w=p-q;
	double t=cross(v,w)/cross(u,v);
	return {p.x+u.x*t,p.y+u.y*t};
}
point get_J(line a,line b){		//重载 
	return get_J(a.a,a.b-a.a,b.a,b.b-b.a); 
}
bool onRight(line a,line b,line c){		//判断a是否在bc交点右面 
	point x=get_J(b,c);
	return area(a.a,a.b,x)<=0; 
}
void half(){
	sort(L+1,L+1+cnt,cmp);
	front=1;tail=0;
	for(int i=1;i<=cnt;i++){
		if(i>=2 && get_angle(L[i-1])==get_angle(L[i])) continue;
		while(tail-front>=1 && onRight(L[i],L[dq[tail-1]],L[dq[tail]])) tail--;
		while(tail-front>=1 && onRight(L[i],L[dq[front]],L[dq[front+1]])) front++;
		dq[++tail]=i;
	}
	while(tail-front>=1 && onRight(L[dq[front]],L[dq[tail-1]],L[dq[tail]])) tail--;
	while(tail-front>=1 && onRight(L[dq[tail]],L[dq[front]],L[dq[front+1]])) front++;
	dq[++tail]=dq[front];
	double ans=0;
	int js=0;
	for(int i=front;i<tail;i++){
		pt[++js]=get_J(L[dq[i]],L[dq[i+1]]);
	} 
	for(int i=2;i+1<=js;i++){
		ans+=area(pt[1],pt[i],pt[i+1]);
	}
	cout<<fixed<<setprecision(3)<<ans/2<<'\n';
}
int main() 
{
	ios;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m;
		for(int j=1;j<=m;j++){
			cin>>pt[j].x>>pt[j].y;
		}
		for(int j=1;j<=m;j++){
			if(j!=m) L[++cnt]={pt[j].x,pt[j].y,pt[j+1].x,pt[j+1].y};
			else L[++cnt]={pt[j].x,pt[j].y,pt[1].x,pt[1].y};
		}
	}
	half();
	return 0;
}
/*


*/