首页 > 代码库 > POJ 1279 Art Gallery 半平面交求多边形核

POJ 1279 Art Gallery 半平面交求多边形核

第一道半平面交,只会写N^2。

将每条边化作一个不等式,ax+by+c>0,所以要固定顺序,方便求解。

半平面交其实就是对一系列的不等式组进行求解可行解。

如果某点在直线右侧,说明那个点在区域内,否则出现在左边,就可能会有交点,将交点求出加入。

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#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;}