典型的凸包问题；
题意是国王建了一座城堡，现在要建围墙，围墙离城堡要有L远，求围墙的长度。
解题思路：
推导公式（1）：
城堡围墙长度最小值 = 城堡顶点坐标构成的散点集的凸包总边长 + 半径为L的圆周长
由于数据规模较大，必须用GrahamScan Algorithm构造凸包（详细的算法可以参考我的POJ2187，这里就不再啰嗦了），然后顺序枚举凸包相邻的两点并计算其距离，得到凸包的总边长，最后加上圆周长2πL
根据圆形的性质,其实就相当于多加了一个r=L的圆，把该圆根据凸包的边数（假设有k条）划分为k段弧，分别用来连接凸包上所有边。这样做的目的就是为了在保证围墙距离城堡至少为L的同时，使得转角处为圆角而不是直角，减少建造围城所需的资源。
附：
针对上面的公式（1）copy一个证明：http://blog.sina.com.cn/s/blog_687916bf0100jq9g.html
证明如下：假如顺时针给出四个点A、B、C、D。组成了凸四边形ABCD。我们不妨过A点作AE垂直于AB，同时过A点再作AF垂直于AD，过B点作BG、BH分别垂直于AB、BC。连结EG，垂线段的长度为L，过A点以AE为半径作一段弧连到AF，同理，使GH成为一段弧。此时EG=AB（边），AB段城墙的最小值为EF+弧EF+弧GH=AB+弧EF+弧GH。对所有点进行同样的操作后，可知城墙的最小值=四边形的周长+相应顶点的弧长（半径都为L）之和。
下面证明这些顶点弧长组成一个圆。依然以前面的四边形为例。A、B、C、D四顶点各成周角，总和为360*4=1440度，四边形内角和为360度，每个顶点作两条垂线，总角度为4*2*90=720度，所以总圆周角为1440-360-720=360度，刚好组成圆。
所以四边形ABCD的围墙最短= 四边形的周长+圆周长。
推广到任意多边形，用同样的方法，城墙最短=凸包的周长 + 以L为半径的圆的周长。
首先，我们得出城墙最短=凸包的周长 + 相应顶点的弧长（半径都为L）之和。
再证明 相应顶点的弧长（半径都为L）之和=以L为半径的圆的周长。
事实上，设凸包顶点为n,n个顶点组成n个周角，角度为360*n=2*180*n，凸包的内角和为180*(n-2)，作了2*n条垂线，和为2*n*90=180*n,所以总圆周角为2*180*n-180*(n-2)-180*n=360，组成圆。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=1005;
const double eps=1e-8;
const double pi=acos(-1.0);//反三角函数，相当于arccos(-1.0);
struct Point
{
int x,y;
}p[MAXN];
int s[MAXN];
int top;
int dblcmp(int d)
{
if(abs(d)<eps)
{
return 0;
}
return d>0?1:-1;
}
bool cmp(const Point &p1,const Point &p2)//排序函数
{
if(p1.y==p2.y)
return p1.x<p2.x;
else
return p1.y<p2.y;
}
int cross(Point & c,Point a,Point b)//叉乘
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
double Distance(Point &a,Point &b)
{
return sqrt(0.0+(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void graham_scan(int n)
{
int i,temp;
sort(p,p+n,cmp);
top=-1;
s[++top]=0;
s[++top]=1;//右链
for(i=2;i<n;i++)
{
while(top>=1&&dblcmp(cross(p[s[top-1]],p[i],p[s[top]]))>=0)
top--;
s[++top]=i;
}
temp=top;
s[++top]=n-2;//左链
for(i=n-3;i>=0;i--)
{
while(top>=temp+1&&dblcmp(cross(p[s[top-1]],p[i],p[s[top]]))>=0)
top--;
s[++top]=i;
}
}
int main()
{
int i,n,l;
double ans;
while(~scanf("%d%d",&n,&l))
{
for(i=0;i<n;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
}
graham_scan(n);
ans=0.0;
for(i=0;i<top;i++)
{
ans+=Distance(p[s[i]],p[s[i+1]]);
}
ans+=2*pi*l;
printf("%.0lf\n",ans);
}
system("pause");//<span style="color: rgb(51, 51, 51); font-family: 'Microsoft Yahei'; font-size: 14px; line-height: 28px; white-space: pre-wrap;">system就是调用从程序中调用系统命令(和shell命令)。 system("pause")就是从程序里调用“</span><a target=_blank data-id="link-to-so" data-c="点击实体词http://wenda.so.com/q/13782873270668431.0.0_1.0.1pause" text="点击实体词" target="_blank" href="http://www.so.com/s?q=pause&ie=utf-8&src=wenda_link" style="margin: 0px; padding: 0px; color: rgb(0, 99, 200); text-decoration: none; font-family: 'Microsoft Yahei'; font-size: 14px; line-height: 28px; white-space: pre-wrap;">pause</a><span style="color: rgb(51, 51, 51); font-family: 'Microsoft Yahei'; font-size: 14px; line-height: 28px; white-space: pre-wrap;">”命令; 而“pause”这个系统命令的功能很简单，就是在命令行上输出一行类似于“Press any key to exit”的字，等待用户按一个键，然后返回</span>
return 0;
}