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

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

# 算法流程

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

# 线点

struct point{
	double x,y;
}pt[MAXN];
struct line{
	point a,b;
}L[MAXN];

# 函数

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

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 凸多边形

# 代码

#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;
}
/*
*/
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝