【模板】凸包

Andrew 算法求凸包

常用的求法有 Graham 扫描法和 Andrew 算法，这里主要介绍 Andrew 算法。

性质

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

过程

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

显然排序后最小的元素和最大的元素一定在凸包上。而且因为是凸多边形，我们如果从一个点出发逆时针走，轨迹总是「左拐」的，一旦出现右拐，就说明这一段不在凸包上。因此我们可以用一个单调栈来维护上下凸壳。

因为从左向右看，上下凸壳所旋转的方向不同，为了让单调栈起作用，我们首先 升序枚举 求出下凸壳，然后 降序 求出上凸壳。

求凸壳时，一旦发现即将进栈的点（( P )）和栈顶的两个点（( S_1, S_2 )，其中 ( S_1 ) 为栈顶）行进的方向向右旋转，即叉积小于 0：

$$\overrightarrow{S_2S_1} \times \overrightarrow{S_1P} < 0$$

则弹出栈顶，回到上一步，继续检测，直到

$$\overrightarrow{S_2S_1} \times \overrightarrow{S_1P} \ge 0$$

或者栈内仅剩一个元素为止。

通常情况下不需要保留位于凸包边上的点，因此上面一段中

$$\overrightarrow{S_2S_1} \times \overrightarrow{S_1P} < 0$$

这个条件中的「<」可以视情况改为 (\le)，同时后面一个条件应改为 (> )。

#include<bits/stdc++.h>
const int N=1e6+12;
using namespace std;
struct point
{
  double x,y;
  bool operator < ( const point &other )
  const
  {
      if( x==other.x )
      {
        return y<other.y;
      }
      return x<other.x;
  }
  double operator *( const point &other )
  const
  {
    return x*other.y-y*other.x;
  }
  point operator - ( const point &other )
  const
  {
    return { x-other.x,y-other.y };
  }
}p[N];
double dis(point p1,point p2)
{
  return sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) );
}
int sta[N],top,n;
bool u[N];
double ans;
int main(){

  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>p[i].x>>p[i].y;
  }

  sort(p+1,p+1+n);
  sta[++top]=1;
  for(int i=2;i<=n;i++)
  {
    while( top>=2 &&
           ( (p[ sta[top] ]-p[ sta[top-1] ]) * ( p[i]-p[sta[top]] ) ) <=0
           )
            u[ sta[top--] ]=0;
    ++top;
    sta[top]=i;
    u[i]=1;
  }
  int tmp=top;
  for(int i=n-1;i;i--)
  {
    if( !u[i] )
    {
        while( top>tmp &&
          ( (p[ sta[top] ]-p[ sta[top-1] ]) * ( p[i]-p[sta[top]] ) ) <=0
           )
            u[ sta[top--] ]=0;
        ++top;
        sta[top]=i;
        u[i]=1;
    }
  }
  sta[top+1]=1;
  for(int i=1;i<=top;i++)
  {
    ans+=dis( p[sta[i]],p[sta[i+1]] );
  }
  printf("%.2lf\n",ans);
}

Graham 扫描法

性质

与 Andrew 算法相同，Graham 扫描法的时间复杂度为 ( O(n\log n) )，复杂度瓶颈也在于对所有点排序。

过程

首先找到所有点中，纵坐标最小的一个点 ( P )。根据凸包的定义我们知道，这个点一定在凸包上。然后将所有的点以相对于点 ( P ) 的极角大小为关键字进行排序。

和 Andrew 算法类似地，我们考虑从点 ( P ) 出发，在凸包上逆时针走，那么我们经过的所有节点一定都是「左拐」的。形式化地说，对于凸包逆时针方向上任意连续经过的三个点 ( P_1, P_2, P_3 )，一定满足：

$$\overrightarrow{P_1 P_2} \times \overrightarrow{P_2 P_3} \ge 0$$

新建一个栈用于存储凸包的信息，先将 ( P ) 压入栈中，然后按照极角序依次尝试加入每一个点。如果进栈的点 ( P_0 ) 和栈顶的两个点 ( P_1, P_2 )（其中 ( P_1 ) 为栈顶）行进的方向「右拐」了，那么就弹出栈顶的 ( P_1 )，不断重复上述过程直至进栈的点与栈顶的两个点满足条件，或者栈中仅剩下一个元素，再将 ( P_0 ) 压入栈中。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+12;
int n,top,sta[N];
struct point
{
  double x,y,ang;
  point operator - ( const point &p ) const
  {
    return {x-p.x,y-p.y,0};
  }
}p[N];
double dis(point p1,point p2)
{
  return sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) );
}
bool cmp(point p1,point p2)
{
  if( p1.ang==p2.ang )
  {
    return dis(p1,p[1])<dis(p2,p[1]);
  }
  return p1.ang<p2.ang;
}
double cross(point p1,point p2)
{
  return p1.x*p2.y-p2.x*p1.y;
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>p[i].x>>p[i].y;
  }
  for(int i=2;i<=n;i++)
  {
    if( p[i].y<p[1].y || ( p[i].y==p[1].y && p[i].x<p[1].x ) )
    {
      swap(p[1],p[i]);
    }
  }
  for(int i=2;i<=n;i++)
  {
    p[i].ang=atan2(p[i].y-p[1].y,p[i].x-p[1].x);
  }
  sort(p+2,p+1+n,cmp);
  sta[++top]=1;
  for(int i=2;i<=n;i++)
  {
    while( top>=2 &&
           cross( p[sta[top]]-p[sta[top-1]],p[i]-p[sta[top]] )<=0
           )
            top--;
    sta[++top]=i;
  }
  sta[top+1]=sta[1];
  double ans=0;
  for(int i=1;i<=top;i++)
  {
    ans+=dis( p[sta[i]],p[sta[i+1]] );
  }
  printf("%.2lf",ans);
}