Art Gallery

题目链接：http://poj.org/problem?id=1279

题意：给出一个n个点的多边形，求多边形核的面积；

思路：先用半平面交求出多边形核的边，再求出多边形核的交点，再用差积求面积即可，如果半平面交的边少于3条，那情况不存在，输出0。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 1e6;
const double EPS = 1e-9;
struct point//点
{
    double x,y;
    point friend operator -(point A,point B)
    {
        return {A.x-B.x,A.y-B.y};
    }
};
struct line//线
{
    point x,y;
};
point p[maxn],q[maxn];
line L[maxn],que[maxn];
double chaj(point A,point B)//差积
{
    return A.x*B.y-A.y*B.x;
}
bool fanx(int N)//判断是否为逆序
{
    double sum=0;
    for(int i=2;i<N;i++)
        sum+=chaj(p[i]-p[1],p[i+1]-p[1]);
    return sum<0;//正序
}
double getAngle(point A)//获得极角角度
{
    return atan2(A.y,A.x);
}
bool cmp(line A,line B)//根据极角排序，极角相同，左边的排到前面
{
    double sum1=getAngle(A.y-A.x);
    double sum2=getAngle(B.y-B.x);
    if (fabs(sum1 - sum2) < EPS)
        return chaj(A.y-A.x,B.y-A.x)<=0;
    return sum1<sum2;
}
point getIntersectPoint(line A, line B)//得到两条线的交点
{
    double a1 = A.x.y - A.y.y, b1 = A.y.x - A.x.x, c1 = A.x.x * A.y.y - A.y.x * A.x.y;
    double a2 = B.x.y - B.y.y, b2 = B.y.x - B.x.x, c2 = B.x.x * B.y.y - B.y.x * B.x.y;
    point PO;
    PO.x= (c1*b2-c2*b1)/(a2*b1-a1*b2);
    PO.y= (a2*c1-a1*c2)/(a1*b2-a2*b1);
    return PO;
}

bool onRight(line A, line B, line C)//判断 b,c 的交点是否在 a 的右边
{
    point o = getIntersectPoint(B, C);
    if( chaj( A.y - A.x ,o - A.x )<0 )
        return true;
    return false;
}
double area(int len)//凸包求面积
{
    if(len<3)
        return 0;
    double sum=0;
    for(int i=3;i<=len;i++)
       sum+=chaj( q[i-1]-q[1] , q[i]-q[1] );
    return fabs(sum/2);
}
void HalfPlaneIntersection(int N)
{
    sort(L+1,L+N+1,cmp);
    int cnt=1;//去重后的个数
    for(int i=2;i<=N;i++)
    {
        if (fabs(getAngle(L[i].y-L[i].x) - getAngle(L[i-1].y-L[i-1].x)) < EPS)
            continue;
        L[++cnt]=L[i];
    }

    int head=0,tail=0;
    for(int i=1;i<=cnt;i++)
    {
        //判断新加入直线产生的影响
        while(tail-head>1 && onRight(L[i], que[tail - 1], que[tail - 2]))
           tail--;
        while(tail-head>1 && onRight(L[i], que[head], que[head + 1]))
            head++;
        que[tail++]=L[i];
    }
    //最后判断最先加入的直线和最后的直线的影响
    while(tail-head>1 && onRight(que[head], que[tail-1], que[tail-2]))
        tail--;
    while(tail-head>1 && onRight(que[tail-1], que[head], que[head+1]))
        head++;
    //半平面交存在que中， head到tail-1
    if(tail-head<3)
    {
        cout<<"0.00"<<endl;
        return ;
    }
    int len=0;
    for(int i=head+1;i<tail;i++)
        q[++len]=getIntersectPoint(que[i],que[i-1]);
    q[++len]=getIntersectPoint(que[head],que[tail-1]);
    printf("%.2lf
",area(len)+EPS);
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int N;
        cin>>N;
        for(int i=1;i<=N;i++)
            cin>>p[i].x>>p[i].y;
        if(fanx(N))//是正序，反正建线
        {
            for(int i=2;i<=N;i++)
            {
                L[i-1].x=p[i];
                L[i-1].y=p[i-1];
            }
            L[N].x=p[1];
            L[N].y=p[N];
        }
        else
        {
            for(int i=1;i<N;i++)
            {
                L[i].x=p[i];
                L[i].y=p[i+1];
            }
            L[N].x=p[N];
            L[N].y=p[1];
        }
        HalfPlaneIntersection(N);
    }
}