数据见底部,我自己的这份AC代码输出了-0.250
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
double eps = 1e-8;
int sgn(double x) { if(fabs(x)<eps) return 0; else return x<0?-1:1; }
struct Point{
double x,y;
Point(){ x=y=0; }
Point(double _x, double _y){ x=_x,y=_y; }
Point operator + (const Point &b) const{ return Point(x+b.x,y+b.y); }
Point operator - (const Point &b) const{ return Point(x-b.x,y-b.y); }
Point operator * (double p) const{ return Point(x*p,y*p); }
Point operator / (double p) const{ return Point(x/p,y/p); }
};
double Cross(const Point &a, const Point &b) { return a.x*b.y-a.y*b.x; }
struct Line{
Point p,v;
double ang;
Line(){}
Line(Point _p,Point _v){
p=_p,v=_v; ang=atan2(v.y,v.x);
}
bool operator < (const Line &l) const {
return ang<l.ang;
}
};
bool Left(const Point &p,const Line &l){
return Cross(l.v,p-l.p)>=0;
}
Point intersection(const Line &a,const Line &b) {
Point x=a.p-b.p; double t=Cross(b.v,x)/Cross(a.v,b.v);
return a.p+a.v*t;
}
//要求闭合。
double halfplane(Line *l,int n,Line *h,Point *p){
sort(l+1,l+n+1); int m,f=1,t=1;
h[1]=l[1];
for(int i=2;i<=n;++i){
while(f<t&&!Left(p[t-1],l[i])) --t;
while(f<t&&!Left(p[f],l[i])) ++f;
if(fabs(Cross(h[t].v,l[i].v))<eps) h[t]=Left(h[t].p,l[i])?h[t]:l[i];
else h[++t]=l[i];
if(f<t) p[t-1]=intersection(h[t-1],h[t]);
}
while(f<t&&!Left(p[t-1],h[f])) --t;
p[t]=intersection(h[f],h[t]);
if(t-f<=1) return 0;
double rs=0;
for(int i=f;i<t;++i)
rs+=Cross(p[i],p[i+1]);
rs+=Cross(p[t],p[f]);
return rs/2;
}
Point p[N]; Line l[N],hp[N];
int n,m,tot;
int main(){
scanf("%d",&m);
while(m--){
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%lf %lf",&p[i].x,&p[i].y);
for(int i=1;i<=n;++i)
l[++tot]=Line(p[i-1],p[i%n]-p[i-1]);
}
printf("%.3lf\n",halfplane(l,tot,hp,p));
}
/*
3
4
0 0
3 0
3 1
0 1
4
4 0
5 0
5 1
4 1
3
0 0
4 0
0 2
*/
实际上这个情况应该是没有交的,面积应该是0吧。