POJ 1279 Art Gallery

半平面交

＊記得注意^算子優先順序

// note ^ operator 
// * operator 

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <algorithm>
#include <functional>

using namespace std;

template<class T>
void pvec(vector<T> val){
    for(int lx = 0;lx < val.size();lx++){
        val[lx].print();
        printf(" ");
    }
    puts("");
    return;
}

const double eps = 1e-7;

struct Point{
    double x, y;
    Point(double _x = 0, double _y = 0):x(_x), y(_y){}
    int id() const {
        if(x > 0 and y >= 0) return 0;
        if(y > 0 and x <= 0) return 1;
        if(x < 0 and y <= 0) return 2;
        if(y < 0 and x >= 0) return 3;
        return -1;
    }
    void print(){ printf("(%.2f,%.2f)", x, y); return; }
};

Point operator+(const Point& a, const Point& b){return Point(a.x + b.x, a.y + b.y);}
Point operator-(const Point& a, const Point& b){return Point(a.x - b.x, a.y - b.y);}
Point operator*(const Point& a, double k){return Point(a.x*k, a.y*k);}
Point operator*(double k, const Point& a){return Point(a.x*k, a.y*k);}
double operator*(const Point& a, const Point& b){return a.x*b.x + a.y*b.y;}
double operator^(const Point& a, const Point& b){return a.x*b.y - a.y*b.x;}

struct Line{
    Point p1, p2, dt;
    Line(Point a = Point(), Point b = Point()):p1(a), p2(b){dt = p2-p1;return;}
    void print(){ p1.print(); printf("->"); p2.print();}
};

bool IsParallel(const Line& a, const Line& b) { return fabs(a.dt^b.dt) < eps; }
bool IsInPlane(const Line& a, const Point& p){ return (a.dt^(p-a.p1)) >= eps; }

bool operator<(const Point& a, const Point& b){
    int ida = a.id(), idb = b.id();
    return (ida != idb) ? ida < idb : 0 < (a^b);
}

typedef vector<Point> Polygon;

Point GetLineInterX(const Line& l1, const Line& l2){
    const Point &a1 = l1.p1, &a2 = l1.p2;
    const Point &b1 = l2.p1, &b2 = l2.p2;
    Point a = a2-a1, b = b2-b1, s = b1-a1;
    return a1 + a*((b^s)/(b^a));
}

bool lcmp(const Line& a, const Line& b){
    return (a.p2-a.p1) < (b.p2-b.p1);
};

Polygon GetPlaneInterX(vector<Line>& _inp){
    if(_inp.size() <= 2) return Polygon();
    sort(_inp.begin(), _inp.end(), lcmp);
    // deal with parellel part
    vector<Line> inp(1, _inp[0]);
    for(int lx = 1;lx < _inp.size();lx++){
        Line& prc_line = inp[(int)inp.size() - 1];
        if(IsParallel(prc_line, _inp[lx])){
            if(IsInPlane(prc_line, _inp[lx].p2))
                prc_line = _inp[lx];
        }else
            inp.push_back(_inp[lx]);
    }
    int sz = inp.size();
    if(sz <= 2) return Polygon();
    
    int qs = 0, qe = 2;
    vector<Line> que(sz+1);
    que[0] = inp[0], que[1] = inp[1];
    for(int lx = 2;lx < sz;lx++){
        while(qe-qs >= 2 and not IsInPlane(inp[lx], GetLineInterX(que[qe-1], que[qe-2]))) qe--;
        while(qe-qs >= 2 and not IsInPlane(inp[lx], GetLineInterX(que[qs]  , que[qs+1]))) qs++;
        que[qe++] = inp[lx];
    }

    while(qe-qs >= 2 and not IsInPlane(que[qs]  , GetLineInterX(que[qe-1], que[qe-2]))) qe--;
    while(qe-qs >= 2 and not IsInPlane(que[qe-1], GetLineInterX(que[qs]  , que[qs+1]))) qs++;
    if(qe-qs <= 2) return Polygon();

    que[qe++] = que[qs];
    Polygon ret;
    for(int lx = qs;lx < qe-1;lx++)
        ret.push_back(GetLineInterX(que[lx], que[lx+1]));
 
    return ret;
}

double GetArea(Polygon a){
    if(a.size() == 0) return 0;
    double ret = 0;
    a.push_back(a[0]);
    for(int lx = 0;lx+1 < a.size();lx++)
        ret += a[lx]^a[lx+1];
    return ret/2;
}

int main(){
    int T; scanf("%d", &T);
    while(T--){
        Polygon hls;
        int n; scanf("%d", &n);
        for(int lx = 0;lx < n;lx++){
            Point inp;
            scanf("%lf %lf", &inp.x, &inp.y);
            hls.push_back(inp);
        }
        if(GetArea(hls) < 0) reverse(hls.begin(), hls.end());
        hls.push_back(hls[0]);
        vector<Line> par;
        for(int lx = 0;lx < n;lx++)
            par.push_back(Line(hls[lx], hls[lx+1]));
         
        Polygon getres = GetPlaneInterX(par);

        printf("%.2f\n", GetArea(getres));

    }
    return 0;
}