【计算几何】求半平面交的面积

【题意】
在一个有限大（-10 0000<=x,y<=10 0000)的平面坐标系上有n个半平面（注意有限的），每个半平面给出一条有向线段（x1,y1)——>(x2,y2）。
每个半平面的有效区域都是左侧。求这n个半平面的交的面积。
【输入文件】
第一行一个整数n（1 <= n <= 2 0000）
下来n个半平面。每个半平面一行四个整数x1,y1,x2,y2。（-100000 <= x1,y1,x2,y2 <= 100000)
【输出文件】
一行，输出n个半平面的交的面积（保留一位小数），如果有效面积不存在则输出"0.0"。
【样例1输入】
3
1 1 9 9
5 10 4 10
0 3 0 2
【样例1输出】
50.0

【样例2输入】
4
0 0 10 0
10 0 10 10
10 10 0 10
11 11 11 0
【样例2输出】
0.0

代码有5个主要函数：
$1.mult()——求叉积$
$2.jd(segment ~~sg1,segment~~ sg2)——求交点$
$3.satisfy(node~ p,segment~~ sg)——判断p是否在sg的左边或线上$
$4.cmp(segment~~ sg1,segment ~~sg2）——按极角排序。（好处是最后得到的边在凸包上有序）$
$5.solve()求解函数$

其实有一个重点不能忽略，就是solve()里面先删队尾，再删对头。为什么呢？

如果要删有向线段的话，由图可知，两个在队列中的有向线段$overrightarrow{AB},overrightarrow{CD}$，$overrightarrow{AB}$的优先级更大。
代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2e4+10;
const double maxx=1e5;
const double minn=-maxx;
const double eps=1e-8;
struct node
{
	double x,y;
}p[N];int pl;
struct segment 
{
	node p1,p2;
	double angle;
	segment(){}
	void get_angle(){angle=atan2(p2.y-p1.y,p2.x-p1.x);}
	segment(double x1,double y1,double x2,double y2){p1=(node){x1,y1};p2=(node){x2,y2};get_angle();}
}seg[N],seglist[N];
int head,tail,n;
double mult(node p1,node p2,node p0)
{
	double x1,y1,x2,y2;
	x1=p1.x-p0.x;
	y1=p1.y-p0.y;
	x2=p2.x-p0.x;
	y2=p2.y-p0.y;
	return x1*y2-x2*y1;
}
node jd(segment sg1,segment sg2)
{
	double t1=mult(sg1.p1,sg2.p2,sg2.p1);
	double t2=mult(sg1.p2,sg2.p2,sg2.p1);
	node p1=sg1.p1,p2=sg1.p2,p;
	p.x=(t1*p2.x-t2*p1.x)/(t1-t2);
	p.y=(t1*p2.y-t2*p1.y)/(t1-t2);
	return p;
}
bool satisfy(node p,segment sg)
{
	return mult(p,sg.p2,sg.p1)<=eps;
}
bool cmp(segment sg1,segment sg2)
{
	if(sg1.angle<sg2.angle)return 1;
	if(sg1.angle-sg2.angle<eps&&satisfy(sg1.p1,sg2)==1)return 1;
	return 0;
}
void solve()
{
	sort(seg+1,seg+n+1,cmp);
	int tp=1;for(int i=2;i<=n;i++)if(seg[i].angle-seg[tp].angle>eps)seg[++tp]=seg[i];
	n=tp;
	head=1;tail=0;
	for(int i=1;i<=n;i++)
	{
		while(head<tail&&satisfy(jd(seglist[tail],seglist[tail-1]),seg[i])==0)--tail;
		while(head<tail&&satisfy(jd(seglist[head],seglist[head+1]),seg[i])==0)++head;
		seglist[++tail]=seg[i];
	}
	while(head<tail&&satisfy(jd(seglist[tail],seglist[tail-1]),seglist[head])==0)--tail;
	while(head<tail&&satisfy(jd(seglist[head],seglist[head+1]),seglist[tail])==0)++head;
	pl=0;
	for(int i=head;i<tail;i++)p[++pl]=jd(seglist[i],seglist[i+1]);
	p[++pl]=jd(seglist[head],seglist[tail]);
	double ans=0;
	for(int i=3;i<=pl;i++)ans+=mult(p[i],p[i-1],p[1]);
	printf("%.1lf
",fabs(ans)/2.0);
}
int main()
{
	scanf("%d",&n);
	seg[1]=segment(minn,minn,maxx,minn);
	seg[2]=segment(maxx,minn,maxx,maxx);
	seg[3]=segment(maxx,maxx,minn,maxx);
	seg[4]=segment(minn,maxx,minn,minn);
	n+=4;
	for(int i=5;i<=n;i++)
	{
		double x1,y1,x2,y2;scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
		seg[i]=segment(x1,y1,x2,y2);
	}
	solve();
	return 0;
}