第一道半平面交，只会写N^2。
将每条边化作一个不等式，ax+by+c>0，所以要固定顺序，方便求解。
半平面交其实就是对一系列的不等式组进行求解可行解。
如果某点在直线右侧，说明那个点在区域内，否则出现在左边，就可能会有交点，将交点求出加入。
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include#include #include #include #include #include #include #include #define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int MAXN = 1555;const double eps = 1e-8;struct POINT{ double x; double y; POINT() : x(0), y(0) {}; POINT(double _x_, double _y_) : x(_x_), y(_y_) {};};struct LINE{ POINT a; POINT b; LINE() {}; LINE(POINT _a_, POINT _b_) : a(_a_), b(_b_) {};};POINT point[MAXN];//记录最开始的多边形POINT temp[MAXN]; //临时保存新切割的多边形POINT ans[MAXN]; //保存新切割出的多边形LINE lline;int n,m;//n的原先的点数,m是新切割出的多边形的点数void Coefficient(const LINE & L, double & A, double & B, double & C){ A = L.b.y - L.a.y; B = L.a.x - L.b.x; C = L.b.x * L.a.y - L.a.x * L.b.y;}double Cross(const POINT & a, const POINT & b, const POINT &o){ return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);}POINT Intersection(const LINE & A, const LINE & B){ double A1, B1, C1; double A2, B2, C2; Coefficient(A, A1, B1, C1); Coefficient(B, A2, B2, C2); POINT temp_point(0, 0); temp_point.x = -(B2 * C1 - B1 * C2) / (A1 * B2 - A2 * B1); temp_point.y = (A2 * C1 - A1 * C2) / (A1 * B2 - A2 * B1); return temp_point;}//求面积，正为顺时针，和叉积写法有关double PointArea(POINT p[],int n){ double area = 0; for(int i = 2; i < n; ++i) area += Cross(p[1], p[i], p[i+1]); return -area / 2.0;}void Cut(){ //用直线ax+by+c==0切割多边形 int cut_m = 0, i; double a, b, c; Coefficient(lline, a, b, c); for(i = 1; i <= m; ++i){ if(a * ans[i].x + b*ans[i].y + c >= 0) //题目是顺时钟给出点的,所以一个点在直线右边的话，那么带入值就会大于等于0 temp[++cut_m] = ans[i]; //说明这个点还在切割后的多边形内，将其保留 else{ if(a * ans[i - 1].x + b * ans[i - 1].y + c > 0){ //该点不在多边形内，但是它和它相邻的点构成直线与 LINE line1(ans[i - 1], ans[i]); //ax+by+c==0所构成的交点可能在新切割出的多边形内， temp[++cut_m] = Intersection(lline, line1); //所以保留交点 } if(a * ans[i + 1].x + b * ans[i + 1].y + c > 0){ LINE line1(ans[i + 1], ans[i]); temp[++cut_m] = Intersection(lline, line1); //所以保留交点 } } } for(i = 1; i <= cut_m; ++i) ans[i] = temp[i]; ans[cut_m + 1] = temp[1]; ans[0] = temp[cut_m]; m = cut_m;}void solve(){ int i; point[0] = point[n]; point[n+1] = point[1]; for(i = 0; i <= n + 1; ++i){ ans[i] = point[i]; } m = n; for(i = 1;i <= n; ++i){ lline.a = point[i]; lline.b = point[i + 1]; //根据point[i]和point[i+1]确定直线ax+by+c==0 Cut(); //用直线ax+by+c==0切割多边形 } printf("%.2f\n",Abs(PointArea(ans,m)));}int main(){ int caseNum,i; scanf("%d",&caseNum); while(caseNum--){ scanf("%d",&n); for(i = 1; i <= n; ++i){ scanf("%lf%lf",&point[i].x,&point[i].y); } solve(); } return 0;}