半平面交模板题。。
依然猥琐地用O(n2)
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=550;
int T;
struct Node {
double x,y;}A,B,C;
Node a[N*2];int m;//图中的点数
Node b[N*2];int mm;
void prepare ()
{m=4;a[1].x=-1001;a[1].y=-1001;a[2].x=1001;a[2].y=-1001;a[3].x=1001;a[3].y=1001;a[4].x=-1001;a[4].y=1001;a[5]=a[1];a[0]=a[4];
}
int n;
double mu (Node a,Node b,Node c)
{double x1=a.x-c.x,y1=a.y-c.y;double x2=b.x-c.x,y2=b.y-c.y;return x1*y2-x2*y1;
}
Node JD (Node x,Node y)
{double t1=mu(x,B,A),t2=mu(y,B,A);Node p;p.x=(t1*y.x-t2*x.x)/(t1-t2);p.y=(t1*y.y-t2*x.y)/(t1-t2);return p;
}
void cut ()
{mm=0;for (int u=1;u<=m;u++){if (mu(B,a[u],A)>0)b[++mm]=a[u];else{if (mu(B,a[u-1],A)>0)b[++mm]=JD(a[u-1],a[u]);if (mu(B,a[u+1],A)>0)b[++mm]=JD(a[u],a[u+1]);}}for (int u=1;u<=mm;u++)a[u]=b[u];a[mm+1]=a[1];a[0]=a[mm];m=mm;
}
int main()
{prepare();scanf("%d",&T);while (T--){scanf("%d",&n);scanf("%lf%lf",&A.x,&A.y);C=A;for (int u=2;u<=n;u++){scanf("%lf%lf",&B.x,&B.y);cut();A=B;}B=C;cut();}double ans=0;for (int u=3;u<=m;u++)ans=ans+mu(a[u],a[u-1],a[1]);printf("%.3lf\n",fabs(ans)/2);return 0;
}