半平面交 板子

半平面交

POJ 2451

敲了个板子，比带花树稍微好一些，但是还是很麻烦...

写了点注释

#include <cstdio>
#include <algorithm>
#include <cmath>
#define Point Vector
const int N=2e4+10;
struct Vector
{
    double x,y;
    Vector(){}
    Vector(double x,double y){this->x=x,this->y=y;}
    double angle(){return atan2(y,x);}//极角
    Vector friend operator *(Vector a,double b){return Vector(a.x*b,a.y*b);}//向量数乘
    Vector friend operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}//向量加
    Vector friend operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}//向量减
}qp[N],ans[N];
const double eps=1e-7;
bool dcmp(double a,double b){return fabs(a-b)<eps;}//是否相等
struct Line
{
    Point s,t;double ang;
    Line(){}
    Line(Point s,Point t){this->s=s,this->t=t,this->ang=(t-s).angle();}
}Li[N],ql[N];
double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}//向量外积
bool cmp(Line a,Line b){return dcmp(a.ang,b.ang)?cross(a.t-a.s,b.t-a.s)+eps<0:a.ang<b.ang;}//极角从小到大排序
bool pingxing(Line a,Line b){return dcmp(cross(a.t-a.s,b.t-b.s),0);}//平行外积为0
Point jiaodian(Line a,Line b){return a.s+(a.t-a.s)*(cross(a.s-b.s,b.t-b.s)/cross(b.t-b.s,a.t-a.s));}//交点，这个要画图
double area(Point *s,int n)//求凸多边形面积
{
    double ret=0;
    s[n+1]=s[1];
    for(int i=1;i<=n;i++) ret+=cross(s[i],s[i+1]);
    return fabs(ret/2);
}
bool isrig(Line a,Point b){return cross(a.t-a.s,b-a.s)+eps<0;}//判断点是否在向量右边
int l,r;
bool SI(Line *li,int n,Point *ret,int &m)//增量法求半平面交
{
    std::sort(li+1,li+1+n,cmp);
    ql[l=r=1]=li[1];
    for(int i=2;i<=n;i++)
        if(!dcmp(li[i].ang,li[i-1].ang))//如果这个直线和上一条极角相等，取前面一条靠左边的
        {
            while(l<r&&isrig(li[i],qp[r-1])) --r;//把队尾超过的点扔了
            while(l<r&&isrig(li[i],qp[l])) ++l;//把队头超过的点扔了
            if(l<=r) qp[r]=jiaodian(ql[r],li[i]);//加入一个交点
            ql[++r]=li[i];//加入直线
            if(l<r&&(pingxing(ql[l],ql[l+1])||pingxing(ql[r],ql[r-1]))) return false;//向量反向，半平面交是直线
        }
    while(l<r&&isrig(ql[l],qp[r-1])) --r;//扔掉队尾不合法的
    while(l<r&&isrig(ql[r],qp[l])) ++l;//扔掉队首不合法的
    if(r-l<=1) return false;//直线少于2个，没得
    qp[r]=jiaodian(ql[l],ql[r]);//首尾交点
    m=0;for(int i=l;i<=r;i++) ret[++m]=qp[i];
    return true;
}
int main()
{
    int n,m;
    scanf("%d",&n);Point a,b,c,d;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
        Li[i]=Line(a,b);
    }
    a=Point(0,0),b=Point(10000,0),c=Point(10000,10000),d=Point(0,10000);
    Li[++n]=Line(a,b),Li[++n]=Line(b,c),Li[++n]=Line(c,d),Li[++n]=Line(d,a);
    if(SI(Li,n,ans,m)) printf("%.1lf
",area(ans,m));
    else puts("0.0");
    return 0;
}