题解：UVA1303 Wall

原题链接

• 洛谷 UVA1303 Wall

题意简述

给定平面上 $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;
}