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

顺时针给你一个多边形...求能看到所有点的面积...用半平面对所有边取交即可,模版题
这里的半平面交是O(n^2)的算法...比较逗比...暴力对每条线段做半平面交...要注意的地方写在注释里了...顺序写反了卡了我好久
/********************* Template ************************/

#include <set>

#include <map>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <queue>

#include <stack>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cassert>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <fstream>

#include <numeric>

#include <iomanip>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define EPS         1e-8

#define MAXN        10005

#define MOD         (int)1e9+7

#define PI          acos(-1.0)

#define INF         ((1LL)<<50)

#define max(a,b)    ((a) > (b) ? (a) : (b))

#define min(a,b)    ((a) < (b) ? (a) : (b))

#define max3(a,b,c) (max(max(a,b),c))

#define min3(a,b,c) (min(min(a,b),c))

#define BUG         cout<<"BUG! "<<endl

#define LLINE        cout<<"------------------"<<endl

#define L(t)        (t << 1)

#define R(t)        (t << 1 | 1)

#define Mid(a,b)    ((a + b) >> 1)

#define lowbit(a)   (a & -a)

#define FIN         freopen("in.txt","r",stdin)

#pragma comment     (linker,"/STACK:102400000,102400000")

// typedef long long LL;

// typedef unsigned long long ULL;

// typedef __int64 LL;

// typedef unisigned __int64 ULL;

// int gcd(int a,int b){ return b?gcd(b,a%b):a; }

// int lcm(int a,int b){ return a*b/gcd(a,b); }

/*********************   F   ************************/

struct POINT{

    double x,y;

    POINT(double _x = , double _y = ):x(_x),y(_y){}

}p[MAXN],q[MAXN],t[MAXN];

int n;

struct LINE{

     double a,b,c;

     POINT A,B;

     LINE(POINT _a, POINT _b):A(_a),B(_b){

        a=B.y-A.y;

        b=A.x-B.x;

        c=B.x*A.y-A.x*B.y;

     }

};

double multiply(POINT sp,POINT ep,POINT op){                //叉积 左+ 右-

    return (sp.x-op.x) * (ep.y-op.y) - (ep.x-op.x) * (sp.y-op.y);

}

POINT Intersection(LINE a,LINE b){                          //直线交点

    double u = fabs(b.A.x * a.a + b.A.y * a.b + a.c);

    double v = fabs(b.B.x * a.a + b.B.y * a.b + a.c);

    POINT t;

    t.x = (b.A.x * v + b.B.x * u) / (u + v);

    t.y = (b.A.y * v + b.B.y * u) / (u + v);

    return t;

}

double Triangle_area(POINT a,POINT b,POINT c){              //求三角形面积(带符号)

    return multiply(a,b,c)/;

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("outm.txt","w",stdout);

    int ct = ;

    int T;

    cin>>T;

    while(T--){

        cin>>n;

        for(int i =  ; i < n ; i++)

            scanf("%lf%lf",&p[i].x,&p[i].y);

        //暴力对每一个向量作半平面交 ...即将右侧的点和与其他直线的交点加入集合

        for(int i =  ; i < n ; i++) q[i] = p[i];

        int cnt = n;

        for(int i =  ; i < n ; i++){

            int c = ;

            for(int j =  ; j < cnt ; j++){

                //点在右侧

                if(multiply(p[i],p[(i+)%n],q[j]) <= EPS) {

                    t[c++] = q[j];

                }else {     //点在左侧,但是前后线段和该直线有交点

                    //这个顺序不要写反,否则不是顺时针会WA

                    if(multiply(p[i],p[(i+)%n],q[(j-+cnt)%cnt]) < -EPS){

                        t[c++] = Intersection(LINE(p[i],p[(i+)%n]) , LINE(q[j],q[(j-+cnt)%cnt]));

                    }

                    if(multiply(p[i],p[(i+)%n],q[(j+)%cnt]) < -EPS){

                        t[c++] = Intersection(LINE(p[i],p[(i+)%n]) , LINE(q[j],q[(j+)%cnt]));

                    }

                }

            }

            for(int j =  ; j < c ; j++) q[j] = t[j];

            cnt = c;

        }

        double area = ;

        for(int i =  ; i < cnt ; i++){

            area += Triangle_area(POINT(,),q[i],q[(i+)%cnt]);

        }

        area = fabs(area);

        printf("%.2lf\n",area);

    }

    return ;

}