关于半平面交

Polygon HPI(Line *v,ll n){
	for(ll i=0;i<n;i++) v[i].ang=Line_angle(v[i]);
	sort(v,v+n);
	Polygon ans;
	Line q[maxp];
	Point p[maxp];
	ll l=0,r=0;
	q[0]=v[0];
	for(ll i=1;i<n;i++){
		while(l<r&&!Onleft(v[i],p[r-1])) r--;
		while(l<r&&!Onleft(v[i],p[l])) l++;
		q[++l]=v[i];
		if(sgn(Cross(q[r].p2,q[l-1].p2))==0){
			r--;
			if(Onleft(q[r],v[i].p1)) q[r]=v[i];
		}
		if(l<r) p[r-1]=Cross_point(q[r-1].p1,q[r-1].p2+q[r-1].p1,q[r].p1,q[r].p2+q[r].p1);
	}
	while(l<r&&!Onleft(q[l],p[r-1])) r--;
	if(r-l<=1) return ans;
	p[r]=Cross_point(q[r].p1,q[r].p2+q[r].p1,q[l].p1,q[l].p2+q[l].p1);
	for(ll i=l;i<=r;i++) ans.p[i-l]=p[i];
	ans.n=r-l+1;
	return ans;
}