http://poj.org/problem?id=1113
题意是给定一个城堡的各个点，然你求出设计一个城墙，包围这个城堡并且保证城墙距离城堡必须大于等于一个给定的距离：
首先是利用图报求出最小的包围城堡的凸多边形，然后求出距离，然后再加上一个整圆就OK了，圆的半径就是给定的距离：（整个思路相当于把凸多边形各个边往外移动距离R，此后连接各边的弧组成一个以R为半径的整圆）；
到此终于把POJ计划的初级阶段刷完了...纪念一下。。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-8;
const int maxn = 1007;
const double pi = acos(-1.0);
struct point
{
double x,y;
}pt[maxn],stack[maxn];
int top;
int cmp(point a,point b)
{
if (a.y != b.y) return a.y < b.y;
else return a.x < b.x;
}
int dblcmp(double x)
{
if (x > eps) return 1;
else if (x < -eps) return -1;
else return 0;
}
double det(double x1,double y1,double x2,double y2)
{
return x1*y2 - x2*y1;
}
double cross(point a,point b,point c)
{
return det(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);
}
//这里起点与终点肯定在凸包上，不知道怎么证明
int graham(point *p,int len)
{
top = 0; int i;
//先排序，lrj黑书上的排序方法
sort(p,p + len,cmp);
stack[top++] = p[0];
stack[top++] = p[1];
//求右链
for (i = 2; i < len; ++i)
{
while (top > 1 && dblcmp(cross(stack[top - 2],stack[top - 1],p[i])) <= 0) top--;
stack[top++] = p[i];
}
//求左链
int tmp = top;
for (i =len - 2; i >= 0; --i)
{
while (top > tmp && dblcmp(cross(stack[top - 2],stack[top - 1],p[i]))<= 0) top--;
stack[top++] = p[i];
}
return top - 1;//起点两次进栈 - 1
}
double dis(point a,point b)
{
double x = a.x - b.x;
double y = a.y - b.y;
return sqrt(x*x + y*y);
}
int main()
{
int n,i,r;
scanf("%d%d",&n,&r);
for (i = 0; i < n; ++i) scanf("%lf%lf",&pt[i].x,&pt[i].y);
int len = graham(pt,n);
double L = 0;
for (i = 0; i < len; ++i)
L += dis(stack[i],stack[(i + 1)%len]);
L = L + 2.0*pi*r;
printf("%.0lf\n",L);
return 0;
}