526互联

二维凸包浅析

发布时间 2023-07-18 19:11:02作者: a_sad_soul

凸包

二维凸包

定义:

凸多边形:凸多边形是指所有内角大小都在\([0,\pi]\)范围内的简单多边形.

凸包:在平面上能包含所有给定点的最小凸多边形叫做凸包

其定义为:对于给定集合\(X\),所有包含\(X\)的凸集的交集\(S\)被称为\(X\)的凸包.

如图,连线构成的凸多边形就是凸包:

\(Andrew\)算法求凸包

性质:

该算法时间复杂度为\(O(nlogn)\)其中\(n\)为待求凸包点集的大小,同时复杂度的瓶颈也在于对所有点坐标的双关键字排序.

过程

首先把所有点以横坐标为第一关键字,纵坐标为第二关键字排序.

显然排序后最小元素和最大元素一定在凸包上.而且因为是凸多边形,我们如果从一个点出发逆时针走,其轨迹总是左拐的,一旦右拐,说明这一段不在凸包上.因此我们可以用一个单调栈维护上下凸壳.因为从左向右看,上下凸壳所旋转的方向不同,为了让单调栈起作用,我们首先升序枚举求出下凸壳,然后降序求出上凸壳.

求凸壳是,一旦发现即将进展的点和栈顶的两个点行进的方向向右旋转,即叉积小于0,则弹出栈顶,回到上一步,继续检测,直到叉积大于等于0或者站内仅剩一个元素为止.

code:

// stk[] 是整型，存的是下标
// p[] 存储向量或点
tp = 0;                       // 初始化栈
std::sort(p + 1, p + 1 + n);  // 对点进行排序
stk[++tp] = 1;
// 栈内添加第一个元素，且不更新 used，使得 1 在最后封闭凸包时也对单调栈更新
for (int i = 2; i <= n; ++i) {
  while (tp >= 2  // 下一行 * 操作符被重载为叉积
        && (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0)
    used[stk[tp--]] = 0;
  used[i] = 1;  // used 表示在凸壳上
  stk[++tp] = i;
}
int tmp = tp;  // tmp 表示下凸壳大小
for (int i = n - 1; i > 0; --i)
  if (!used[i]) {
    // ↓求上凸壳时不影响下凸壳
    while (tp > tmp && (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0)
      used[stk[tp--]] = 0;
    used[i] = 1;
    stk[++tp] = i;
  }
for (int i = 1; i <= tp; ++i)  // 复制到新数组中去
  h[i] = p[stk[i]];
int ans = tp - 1;

看看模板题

,不多解释,直接上代码

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
struct node{
    double x,y;
}in[MAXN];
bool cmp(node a,node b)
{
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
stack<int>a,b;
double mult(double x1,double y1,double x2,double y2)
{
    return x1*y2-x2*y1;
}
double SQ(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int ansline[MAXN*2+10];
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        scanf("%lf%lf",&in[i].x,&in[i].y);
    }
    sort(in+1,in+1+n,cmp);
    stack<int>a;
    a.push(1);
    for(int i=2;i<=n;++i)
    {
        if(a.size()==1)
        {
            a.push(i);
            continue;
        }
        while(a.size()>1){
        int S1=a.top();
        a.pop();
        int S2=a.top();
        a.push(S1);
        if(mult(in[S1].x-in[S2].x,in[S1].y-in[S2].y,in[i].x-in[S1].x,in[i].y-in[S1].y)<0)a.pop();
        else break;
        }
        a.push(i);
    }
    int l=a.size();
    for(int i=1;i<=l;++i)
    {
        ansline[i]=a.top();a.pop();
    }
    a.push(n);
    for(int i=n-1;i>=1;--i)
    {
        if(a.size()==1)
        {
            a.push(i);
            continue;
        }
        while(a.size()>1){
        int S1=a.top();
        a.pop();
        int S2=a.top();
        a.push(S1);
        if(mult(in[S1].x-in[S2].x,in[S1].y-in[S2].y,in[i].x-in[S1].x,in[i].y-in[S1].y)<0)a.pop();
        else break;
        }
        a.push(i);
    }
    int g=a.size();
    for(int i=1;i<=g;++i)
    {
        ansline[i+l]=a.top();a.pop();
    }
    double ans=0;
    for(int i=1;i<l+g;++i)
    {
        ans+=SQ(in[ansline[i]].x,in[ansline[i]].y,in[ansline[i+1]].x,in[ansline[i+1]].y);
        //cout<<ansline[i]<<" ";
    }
    //ans+=SQ(in[ansline[l+g]].x,in[ansline[l+g]].y,in[ansline[1]].x,in[ansline[1]].y);
    //cout<<SQ(in[ansline[l+g]].x,in[ansline[l+g]].y,in[ansline[1]].x,in[ansline[1]].y)<<endl;
    printf("%.2lf\n",ans);
    return 0;
}

再上一道变式题(来源:【JZOJ NOIP2019模拟2019.9.4】A )

题解:

自己写的代码:(有点丑,别介意)

    #include<bits/stdc++.h>
    #define MAXN 1000005
    using namespace std;
    int n,q;
    struct node
    {
        long long a,b;
    };
    long long f(node a,long long x)
    {
        return a.a*x+a.b;   
    }

    bool cmp(node a,node b)
    {
        if(a.a==b.a)return a.b<b.b;
        return a.a<b.a;
    }
    node u[MAXN],d[MAXN],stu[MAXN],Std[MAXN];
    int cntu,cntd;
    long long mult(long long x1,long long y1,long long x2,long long y2)
    {
        return x1*y2-x2*y1;
    }
    void tubao(node U[],int n,node st[],int &cnt)
    {
        sort(U+1,U+n+1,cmp);
        for(int i=1;i<=n;++i)
        {
            while((cnt>=1&&st[cnt].a==U[i].a)|| ((st[cnt-1].b-st[cnt].b)*(U[i].a-st[cnt-1].a)-(st[cnt-1].b-U[i].b)*(st[cnt].a-st[cnt-1].a)>=0)&&cnt>=2)
                    cnt--;
            //依旧是叉乘,然后可以把ax+b看成是点(a,b),这样就转化为正常求凸包了
            st[++cnt]=U[i]; 
        }

    }
    int sum;
    long long divide(node S[],int cnt,int x)
    {
        int l=1,r=cnt;
        while(l<=r)
        {//++sum;
            int mid=(l+r)>>1;
            if(f(S[mid],x)>f(S[mid+1],x))
                r=mid-1;
            else {l=mid+1;}
        }
        return f(S[l],x)*x;
    }

    long long read()
    {
        long long x=0,f=1;char ch=0;
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
        return f*x;
    }
    int main()
    {
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
        cin>>n>>q;
        for(int i=1;i<=n;++i)
        {
            node in;
            in.a=read(),in.b=read();
            u[i]=in;
            in.a=-in.a,in.b=-in.b;
            d[i]=in; 
        }
        tubao(u,n,stu,cntu);
        tubao(d,n,Std,cntd);
        while(q--)
        {
            long long x;
            scanf("%lld",&x);
            if(x>0)printf("%lld",divide(stu,cntu,x));
            else printf("%lld",-divide(Std,cntd,x));
            putchar('\n');
        }
        //cout<<sum<<endl;
        return 0;
    }