半平面交

代码

#include<bits/stdc++.h> 
using namespace std;
typedef double db;
const int N = 1e5+1;

int n,cnt;

struct P{
	db x,y;
	P(db _x=0,db _y=0){x=_x;y=_y;}
	friend P operator - (P a,P b){return P(a.x-b.x,a.y-b.y);}
	friend db operator * (P a,P b){return a.x*b.y-b.x*a.y;}
}ans[N];

struct L{
	P a,b;
	db k;
	L(P _a=P(0,0),P _b=P(0,0),db _k=0){a=_a;b=_b;k=_k;}
	friend bool operator < (L a,L b){
		if(a.k==b.k)return (b.b-a.a)*(b.a-a.a)<=0;
		return a.k<b.k;
	}
}a[N],q[N];

P inter(L a,L b){
	db k1,k2,t;
	k1=(a.b-b.a)*(b.b-b.a);
	k2=(b.b-b.a)*(a.a-b.a);
	t=k1/(k1+k2);
	P ans;
	ans.x=a.b.x+(a.a.x-a.b.x)*t;
	ans.y=a.b.y+(a.a.y-a.b.y)*t;
	return ans;
}

bool jud(L a,L b,L t){
	P p=inter(a,b);
	return (t.a-p)*(t.b-p)<0;
}

void hpi(){
	sort(a+1,a+n+1);
	int tot=0;
	for(int i=1;i<=n;++i)if(a[i].k!=a[tot].k)a[++tot]=a[i];
	n=tot;
	int L=0,R=1;
	q[0]=a[1];q[1]=a[2];
	for(int i=3;i<=n;++i){
		while(L<R&&jud(q[R],q[R-1],a[i]))R--;
		while(L<R&&jud(q[L],q[L+1],a[i]))L++;
		q[++R]=a[i];
	}
	while(L<R&&jud(q[R],q[R-1],q[L]))R--;
	while(L<R&&jud(q[L],q[L+1],q[R]))L++;
	q[R+1]=q[L];
	for(int i=L;i<=R;++i)ans[++cnt]=inter(q[i],q[i+1]);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lf%lf%lf%lf",&a[i].a.x,&a[i].a.y,&a[i].b.x,&a[i].b.y);
	a[++n]=L(P(0,0),P(10000,0),0);a[++n]=L(P(10000,0),P(10000,10000),0);
	a[++n]=L(P(10000,10000),P(0,10000),0);a[++n]=L(P(0,10000),P(0,0),0);
	for(int i=1;i<=n;++i)a[i].k=atan2((a[i].b.y-a[i].a.y),(a[i].b.x-a[i].a.x));
	hpi();
	db res=0;
	if(cnt>=3){
		ans[++cnt]=ans[1];
		for(int i=1;i<=cnt;++i)res+=ans[i]*ans[i+1];
		res=fabs(res)/2;
	}
	printf("%.1lf",res);
	return 0;
}