发布时间：2024-07-31

半平面交(求凸多边形的交集)

struct Line{//存储凸包上每条线段的起点和终点
    Point st,ed;
    Line(Point _st=Point(),Point _ed=Point()):st(_st),ed(_ed){}
};

double line_get_angle(const Line& a){
    return atan2(a.ed.y-a.st.y,a.ed.x-a.st.x);
}

bool line_cmp(const Line& a, const Line& b){
    double A=line_get_angle(a),B=line_get_angle(b);
    if (!cmp(A,B)) return area(a.st,a.ed,b.ed)<0;
    return A<B;
}

Point get_line_intersection(Line a,Line b){
    return get_line_intersection(a.st,a.ed-a.st,b.st,b.ed-b.st);
}

bool on_right(Line& a, Line& b, Line& c){//判断bc的交点是否在a的右侧
    auto o = get_line_intersection(b,c);
    return sign(area(a.st,a.ed,o))<=0;
    //需要保留经过半平面交的所有直线的时候，将该处等号去掉
}
int dq[N];// 双端队列
double half_plane_intersection(vector<Line> &line){
    sort(line.begin(),line.end(),line_cmp);//对每条直线按照极坐标进行排序
    int hh=0,tt=-1;//定义双端队列对头和队尾元素
    for(int i=0;i<line.size();i++)//遍历每一条直线
    {
        if (i&&!cmp(line_get_angle(line[i]),line_get_angle(line[i-1]))) continue;//当两直线极坐标角度相同
        while(hh+1<=tt&&on_right(line[i],line[dq[tt-1]],line[dq[tt]])) tt--;
        //如果line[l[tt-1]]和line[l[tt]]的交点在line[i]的右侧,删除队尾元素
        while(hh+1<=tt&&on_right(line[i],line[dq[hh]],line[dq[hh+1]])) hh++;
        //如果line[l[hh]]和line[l[hh+1]]的交点在line[i]的右侧,删除队头元素
        dq[++tt]=i;//将该直线加入队尾
    }
    //判断一下第一条直线与最后一条直线
    while (hh+1<=tt&&on_right(line[dq[hh]],line[dq[tt-1]],line[dq[tt]])) tt--;//队尾更新队头
    while (hh+1<=tt&&on_right(line[dq[tt]],line[dq[hh]],line[dq[hh+1]])) hh++;//队头更新队尾

    dq[++tt]=dq[hh];//将第一条直线再次加入双端队列末尾

    //计算半平面交交点
    vector<Point> ans;
    for (int i=hh;i<tt;i++){ //对于半平面交上的直线两两之间求出交点
        ans.push_back(get_line_intersection(line[dq[i]],line[dq[i+1]]));
    }
    //计算半平面交面积
    return polygon_area(ans);
}