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.