凸包

参考资料

• 凸包 - OI Wiki
• 凸包 - 维基百科

Andrew 算法

#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 扫描法

#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

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

Code (1)

#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;
}

洛谷 P2116 城墙

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

Code (1)

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

const double pi=acos(-1);
const int N=1005;
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,l;
	cin>>n>>l;
	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=l*pi*2;
	for(int i=1;i<=m;i++)ans+=Dis(a[s[i]],a[s[i%m+1]]);
	cout<<int(ans+0.5)<<'\n';
	return 0;
}

洛谷 P3829 [SHOI2012] 信用卡凸包

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

Code (1)

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

const double pi=acos(-1);
const int N=10005;
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);}
	Point operator-(Point B){return Point(x-B.x,y-B.y);}
}a[N<<2];
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;}
Point rotate(Point A,double t){return Point(A.x*cos(t)-A.y*sin(t),A.x*sin(t)+A.y*cos(t));}
bool cmp(Point A,Point B)
{
	return A.x!=B.x?A.x<B.x:A.y<B.y;
}
int s[N<<2];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	double A,B,r;
	cin>>n>>A>>B>>r;
	A=A/2-r;B=B/2-r;
	for(int i=1;i<=n;i++)
	{
		Point P;
		double t;
		cin>>P.x>>P.y>>t;
		a[i*4-3]=rotate({B,A},t)+P;
		a[i*4-2]=rotate({B,-A},t)+P;
		a[i*4-1]=rotate({-B,A},t)+P;
		a[i*4]=rotate({-B,-A},t)+P;
	}
	n<<=2;
	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=r*pi*2;
	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;
}

洛谷 UVA1303 Wall

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

Solution

题意简述

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

解题思路

凸多边形是指所有内角大小都在 $[0,\pi]$ 范围内的简单多边形。在平面上能够包含所有给定点的最小凸多边形称为 凸包，因此不会出现类似 $\angle GHF$ 这种凹角的情况。

引用 @Heartlessly 制作的图示：

整个外轮廓由 线段 和 圆弧 组成。

每条线段（红色）的长度都等于多边形（凸包）对应边（蓝色）的长度，因此所有线段的总长度正好等于凸包的周长。

每段圆弧的长度与对应圆心角成正比。对于每个类似 $\angle BAC$ 的角，我们可以表示为：

$$\angle BAC=2\pi-\angle DAE-\angle BAD-\angle CAE=\pi-\angle DAE$$

注意到 $\pi-\angle DAE$ 恰好等于 $\angle DAE$ 的外角，而多边形所有外角之和为 $2\pi$。因此，所有圆弧的总长度等于一个半径为 $L$ 的圆的周长，即 $2\pi L$。

使用 Andrew 算法 或 Graham 扫描法 计算凸包的周长，再加上 $2\pi L$，即为最终结果。

参考代码

Andrew 算法

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

const double pi=acos(-1);
const int N=1005;
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 T;
	cin>>T;
	while(T--)
	{
		int n,l;
		cin>>n>>l;
		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=l*pi*2;
		for(int i=1;i<=m;i++)ans+=Dis(a[s[i]],a[s[i%m+1]]);
		cout<<int(ans+0.5)<<'\n';
		if(T)cout<<'\n';
	}
	return 0;
}

Graham 扫描法

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

const double pi=acos(-1);
const int N=1005;
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 T;
	cin>>T;
	while(T--)
	{
		int n,l;
		cin>>n>>l;
		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=l*pi*2;
		for(int i=1;i<=m;i++)ans+=Dis(a[s[i]],a[s[i%m+1]]);
		cout<<int(ans+0.5)<<'\n';
		if(T)cout<<'\n';
	}
	return 0;
}