Code
#include<iostream>
#include<cmath>
#include<algorithm>
#define eps 1e-3
using namespace std;
struct PT
{
double x,y;
}p[1010],p2[1010];
int N,L;
double Cha(PT a,PT b,PT c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double dist(PT a,PT b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(PT a,PT b)
{
if(Cha(p[0],a,b)==0)
return dist(p[0],a)<dist(p[0],b);
else return Cha(p[0],a,b)>0;
}
int main()
{
int i,j;
scanf("%d%d",&N,&L);
int sw=0;
for(i=0;i<N;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for(i=1;i<N;i++)
{
if(p[i].y<p[sw].y||p[i].y==p[sw].y&&p[i].x<p[sw].x)
sw=i;
}
p2[0]=p[sw];
p[sw]=p[0];
p[0]=p2[0];
sort(p+1,p+N,cmp);
int top=1;
p2[0]=p[0];
p2[1]=p[1];
for(i=2;i<N;i++)
{
while(top>=1&&Cha(p2[top-1],p2[top],p[i])<0)
top--;
p2[++top]=p[i];
}
double len=0;
for(i=0;i<=top;i++)
{
len+=sqrt(dist(p2[i],p2[(i+1)%(top+1)]));
}
len+=2*L*acos(-1.0);
printf("%.0lf\n",len);
return 0;
}
题意为建一个周长最短的城墙，使多边形的任意一点到城墙的距离都>L。
首先求凸包(画个凸包就能看出来，三角形两边之和大于第三边，凸包的形状最优)
然后每个顶点用圆弧连接，从圆弧的两个端点向凸包的边做垂线可以看出，圆弧的总的角度为n*360-(n-2)*180*2=360.
最后的答案为凸包长度+2*pi*L.