半平面交


半平面交


定义

二维平面上有若干个直线,我们不断删除右侧的空间直到所有的直线全部迭代完剩下的就是所求半平面

  1. 先将所有的向量按角度排序(atan2(y,x))
  2. 按顺序从左至右扫描所有的向量,用双端队列去维护
  3. 只要新的交点在前一个交点的左侧就一直替代,双端都要迭代

模板

逆时针给出 n 个凸多边形的顶点坐标,求它们交的面积。第一行有一个整数 n,表示凸多边形的个数,以下依次描述各个多边形。第 i 个多边形的第一行包含一个整数 mi,表示多边形的边数,以下 mi 行每行两个整数,逆时针给出各个顶点的坐标。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<double,double> PDD;
const int N = 510;
const double eps=1e-8;
int cnt;
struct Line
{
    PDD st,ed;
}line[N];
PDD pg[N],ans[N];
int q[N];
int sign(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
int dcmp(double x,double y)
{
    if(fabs(x-y)<eps)   return 0;
    return x<y?-1:1;
}
double get_angle(const 	Line& a)
{
    return atan2(a.ed.y-a.st.y,a.ed.x-a.st.x);
}
PDD operator - (PDD a,PDD b)
{
    return {a.x-b.x,a.y-b.y};
}
double cross(PDD a,PDD b)
{
    return a.x*b.y-a.y*b.x;
}
double area(PDD a,PDD b,PDD c)
{
    return cross(b-a,c-a);
}
bool cmp(const Line& a,const Line& b)
{
    double A=get_angle(a),B=get_angle(b);
    if(!dcmp(A,B))  return area(a.st,a.ed,b.ed)<0;
    return dcmp(A,B)==-1;
}
PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w)
{
    auto u=p-q;
    double t=cross(w,u)/cross(v,w);
    return {p.x+v.x*t,p.y+v.y*t};
}
PDD 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)
{
    auto o=get_line_intersection(b,c);
    return sign(area(a.st,a.ed,o))<=0;
}
double half_plane_intersection()
{
    sort(line,line+cnt,cmp);
    int hh=0,tt=-1;
    for(int i=0;i<cnt;i++)
    {
        if(i&&!dcmp(get_angle(line[i]),get_angle(line[i-1])))   continue;
        while(hh+1<=tt&&on_right(line[i],line[q[tt-1]],line[q[tt]]))   tt--;
        while(hh+1<=tt&&on_right(line[i],line[q[hh]],line[q[hh+1]]))    hh++;
        q[++tt]=i;
    }
    while(hh+1<=tt&&on_right(line[q[hh]],line[q[tt-1]],line[q[tt]]))    tt--;
    while(hh+1<=tt&&on_right(line[q[tt]],line[q[hh]],line[q[hh+1]]))    hh++;
    q[++tt]=q[hh];
    int k=0;
    for(int i=hh;i<tt;i++)
        ans[k++]=get_line_intersection(line[q[i]],line[q[i+1]]);
    double res=0;
    for(int i=1;i+1<k;i++)
        res+=area(ans[0],ans[i],ans[i+1]);
    return res/2;
}
int main()
{
    int n,m;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&m);
        for(int i=0;i<m;i++)    scanf("%lf%lf",&pg[i].x,&pg[i].y);
        for(int i=0;i<m;i++)    line[cnt++]=(Line){pg[i],pg[(i+1)%m]};
    }
    double res=half_plane_intersection();
    printf("%.3lf",res);
    return 0;
}


文章作者: Dydong
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Dydong !
  目录