Skip to main content

凸包

参考资料​

简介​

凸包（Convex Hull）是包含平面点集所有点的最小凸多边形。常用 Andrew 与 Graham 两种算法，均为 O(nlog⁡n)O(n\log n)。

Andrew 算法​

Andrew 算法先把点按坐标排序，再用单调栈分别求下凸壳与上凸壳：加入新点时，若它与栈顶两点构成非左转（叉积不为正）就弹栈。瓶颈在排序，时间复杂度为 O(nlog⁡n)O(n\log n)。

931 Bcpp
#include <bits/stdc++.h>
using namespace std;

const int N=100005;
struct Point
{
	double x,y;
	Point(){}
	Point(double _x,double _y):x(_x),y(_y){}
	Point operator-(Point B){return Point(x-B.x,y-B.y);}
}a[N];
double Dis(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
bool cmp(Point A,Point B)
{
	return A.x!=B.x?A.x<B.x:A.y<B.y;
}
int s[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+n+1,cmp);
	int m=0;
	for(int i=1;i<=n;i++)
	{
		while(m>1&&Cross(a[s[m]]-a[s[m-1]],a[i]-a[s[m]])<=0)m--;
		s[++m]=i;
	}
	int t=m;
	for(int i=n-1;i>=1;i--)
	{
		while(m>t&&Cross(a[s[m]]-a[s[m-1]],a[i]-a[s[m]])<=0)m--;
		s[++m]=i;
	}
	if(m>1)m--;
	double ans=0;
	for(int i=1;i<=m;i++)ans+=Dis(a[s[i]],a[s[i%m+1]]);
	cout<<fixed<<setprecision(2)<<ans<<'\n';
	return 0;
}

Graham 扫描法​

Graham 扫描法取最低（同高取最左）的点为基准，把其余点按相对它的极角排序，再用栈依次扫描：遇到右转就弹栈。时间复杂度为 O(nlog⁡n)O(n\log n)。

911 Bcpp
#include <bits/stdc++.h>
using namespace std;

const int N=100005;
struct Point
{
	double x,y;
	Point(){}
	Point(double _x,double _y):x(_x),y(_y){}
	Point operator-(Point B){return Point(x-B.x,y-B.y);}
}a[N];
double Dis(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
bool cmp(Point A,Point B)
{
	double t=Cross(A-a[1],B-a[1]);
	return t!=0?t>0:Dis(A,a[1])<Dis(B,a[1]);
}
int s[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
		if(a[i].y!=a[1].y?a[i].y<a[1].y:a[i].x<a[1].x)swap(a[i],a[1]);
	}
	sort(a+2,a+n+1,cmp);
	int m=0;
	for(int i=1;i<=n;i++)
	{
		while(m>1&&Cross(a[s[m]]-a[s[m-1]],a[i]-a[s[m]])<=0)m--;
		s[++m]=i;
	}
	double ans=0;
	for(int i=1;i<=m;i++)ans+=Dis(a[s[i]],a[s[i%m+1]]);
	cout<<fixed<<setprecision(2)<<ans<<'\n';
	return 0;
}

例题​

洛谷 P2742 【模板】二维凸包 / [USACO5.1] 圈奶牛Fencing the Cows

给定平面上 nn 个点，求凸包周长。

洛谷 P2116 城墙

在城堡外修建一堵围墙，要求围墙离城堡的最近距离不能少于 LL，求出最少需要修建多长的围墙。

洛谷 P3829 [SHOI2012] 信用卡凸包

给定平面上一些规格相同的信用卡，求其凸包的周长。

洛谷 UVA1303 Wall

给定平面上 nn 个点，求出最短的包围所有点的轮廓且满足任意点到轮廓的距离不小于给定的 LL。