UVA1303 Wall 题解

UVA1303 Wall 题解

凸包裸题

解法

结论

答案是凸包长度和一个直径是 L L L 的圆周长的和，如图。

黑色实线即为答案所求的轮廓的长度。

因为题中要求轮廓到所有点的距离大于等于 L L L，显然我们要控制所有凸包上的点到轮廓的距离等于 L L L。我们自然想到了如图的方法，把凸包平移出去 L L L 的长度，在有点的地方，轮廓即为一段圆弧。因为凸包多凸多边形，而凸多边形的外角和为 36 0 ∘ 360^{\circ} 360∘，所以所有圆弧长度和等于一个直径为 L L L 的圆的周长。

为什么要选凸包

如果不选凸包而选一个凹进去的形状，如图，显然答案的折现比凹进去的点 Q , O , T , U , R Q,O,T,U,R Q,O,T,U,R 连成的线更优。

代码

#include<bits/stdc++.h>
int t,n,beginning,L;
double ans,pi=acos(-1),bx,by;
struct point
{
	double x,y,deg;
	point()
	{
		x=0x3f3f3f3f,y=0x3f3f3f3f;
	}
	point(int x,int y)
	{
		this->x=x,this->y=y;
	}
	inline void calc()
	{
		if(x==0)
		{
			if(y==0) deg=0;
			else deg=90;
		}else deg=atan2(y,x)*180/pi;
	}
	inline friend double distance(const point &lhs,const point &rhs)
	{
		return sqrt((lhs.x-rhs.x)*(lhs.x-rhs.x)+(lhs.y-rhs.y)*(lhs.y-rhs.y));
	}
	inline bool operator<(const point &rhs) const
	{
		if(deg==rhs.deg) return distance((point){0,0},*this)<distance((point){0,0},rhs);
		return deg<rhs.deg;
	}
};
point a[10010];
std::vector<point> v;
inline int min(const int &lhs,const int &rhs)
{
	if(a[lhs].y==a[rhs].y) return a[lhs].x<a[rhs].x?lhs:rhs;
	return a[lhs].y<a[rhs].y?lhs:rhs;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&L),beginning=0,v.clear();
		for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y),beginning=min(beginning,i);
		bx=a[beginning].x,by=a[beginning].y;
		for(int i=1;i<=n;i++) a[i].x-=bx,a[i].y-=by,a[i].calc();
		std::swap(a[1],a[beginning]),std::sort(a+2,a+n+1),a[++n]=a[1],v.push_back(a[1]),v.push_back(a[2]);
		ans=distance(v[0],v[1]);
		for(int i=3;i<=n;i++)
		{
			while(1)
			{
				if((a[i].x-v[v.size()-2].x)*(v.back().y-v[v.size()-2].y)>(v.back().x-v[v.size()-2].x)*(a[i].y-v[v.size()-2].y))
					ans-=distance(v.back(),v[v.size()-2]),v.pop_back();
				else break;
			}
			v.push_back(a[i]),ans+=distance(v.back(),v[v.size()-2]);
		}
		printf("%.0lf\n",ans+pi*L*2);
		if(t) printf("\n");
	}
	return 0;
}