主要计算半平面交

//半平面交
struct halfplane:public Line
{
    double angle;
    halfplane(){}
    //表示向量 s->e 逆时针 (左侧) 的半平面
    halfplane(Point ss,Point ee)
    {
        s=ss,e=ee;
    }
    halfplane(Line v)
    {
        s=v.s;
        e=v.e;
    }
    void calc_angle(void)
    {
        angle=atan2(e.y-s.y,e.x-s.x);
    }
    bool operator <(const halfplane &b) const
    {
        return angle<b.angle;
    }
};

struct halfplanes
{
    int n;
    halfplane hp[maxp];
    Point p[maxp];
    int que[maxp];
    int st,ed;

    halfplanes()
    {
        n=0;
    }
    void push(halfplane tmp)
    {
        hp[n++]=tmp;
    }

    //去重
    void _unique(void)
    {
        int m=1;
        for(int i=1;i<n;i++)
        {
            if(sgn(hp[i].angle-hp[i-1].angle)!=0)
                hp[m++]=hp[i];
            else if(sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0)
                hp[m-1]=hp[i];
        }
        n=m;
    }

    bool halfplane_insert(void)
    {
        for(int i=0;i<n;i++) hp[i].calc_angle();
        sort(hp,hp+n);
        _unique();

        que[st=0]=0;
        que[ed=1]=1;
        p[1]=hp[0].cross_point(hp[1]);
        for(int i=2;i<n;i++)
        {
            while(st<ed&&sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0) ed--;
            while(st<ed&&sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0) st++;
            que[++ed]=i;
            if(hp[i].parallel(hp[que[ed-1]])) return false;
            p[ed]=hp[i].cross_point(hp[que[ed-1]]);
        }
        while(st<ed&&sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0) ed--;
        while(st<ed&&sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0) st++;

        if(st+1>=ed) return false;
        return true;
    }

    //得到最后半平面交得到的凸多边形
    //需要先调用 halfplaneinsert() 且返回 true
    void get_convex(polygon &con)
    {
        p[st]=hp[que[st]].cross_point(hp[que[ed]]);
        con.n=ed-st+1;
        for(int j=st,i=0;j<=ed;i++,j++)
            con.p[i]=p[j];
    }

};