#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const double eps=1e-8;
int DoubleCompare(double x) { //精度三出口判断与0关系
	if(fabs(x)<eps)return 0; //=0
	else if(x<0)return -1; //<0
	else return 1; //>0
}
struct Point {
	double x,y;
	Point(double _x,double _y):x(_x),y(_y){}
	Point(){}
	Point operator + (const Point& a) const {
		return Point(x+a.x,y+a.y);
	}
	Point operator - (const Point& a) const {
		return Point(a.x-x,a.y-y);
	}
	Point operator * (const double a) const {
		return Point(x*a,y*a);
	}
} ;
typedef Point Vector;
double Cross(Vector a,Vector b) { //叉积
	return a.x*b.y-b.x*a.y;
}
double Area(Point a,Point b,Point c) { //三点的平行四边形有向面积
	Vector u=b-a,v=c-a;
	return Cross(u,v);
}
double Area(int n,Point* P) { //计算多边形有向面积（剖分法） 
	double ans=0;
	for(int i=2; i<n; i++)ans+=Area(P[1],P[i],P[i+1]);
	return ans/2;
}
struct Line { //有向直线，左边为半平面
	Point p; //直线上任意一点
	Vector v; //方向向量
	double ang;
	Line() {}
	Line(Point p,Vector v):p(p),v(v) {
		ang=atan2(v.y,v.x);
	}
	bool operator < (const Line& L) const {
		return ang<L.ang;
	}
};
bool OnLeft(Line L,Point p) { //判断点p是否在有向直线L左边（若不舍直线上的点则加上等号） 
	return DoubleCompare(Cross(L.v,L.p-p))>=0;
}
Point GetIntersection(Line a,Line b) {
	Vector u=a.p-b.p;
	double t=Cross(u,b.v)/Cross(a.v,b.v);
	return a.p+a.v*t;
}
int HalfplaneIntersection(int n,Line* L,Point* poly) {
	sort(L+1,L+n+1); //极角排序
	int first=1,last=1;
	Point p[n+5];
	Line q[n+5];
	q[last]=L[1];
	for(int i=2; i<=n; i++) {
		while(first<last&&!OnLeft(L[i],p[last-1]))last--;
		while(first<last&&!OnLeft(L[i],p[first]))first++;
		q[++last]=L[i];
		if(fabs(Cross(q[last].v,q[last-1].v))<eps) { //平行同向，取内侧 
			last--;
			if(!OnLeft(L[i],p[last-1]))q[last]=L[i];
		}
		if(first<last)p[last-1]=GetIntersection(q[last-1],q[last]);
	}
	while(first<last&&!OnLeft(q[first],p[last-1]))last--; //删除无用平面
	if(last-first<=1)return 0; //空集
	p[last]=GetIntersection(q[last],q[first]);
	int m=0;
	for(int i=first; i<=last; i++)poly[++m]=p[i]; 
	return m; 
}
///////////////
Point a[10005],p[10005];
Line l[10005];
int n,m,sum=0,k;
int main() {
	k=Get_Int();
	while(k--) {
		scanf("%d",&n);
		sum=0;
		for(int i=1; i<=n; i++)scanf("%lf%lf",&p[i].x,&p[i].y);
		l[++sum]=Line(p[1],p[1]-p[n]);
		for(int i=2; i<=n; i++)l[++sum]=Line(p[i],p[i]-p[i-1]);
		int cnt=HalfplaneIntersection(sum,l,p);
		printf("%0.2lf\n",fabs(Area(cnt,p)));
	}
	return 0;
}

• 1474都过了 这个过不了 (0) Yang_Ming 2017-01-25 22:08:50
• Re:求救，nlogn半平面交模板过不了 (3030) 20181gdgzoi236 2019-07-04 21:25:06