Link：http://poj.org/problem?id=1113
Graham法求凸包（O(Nlog2N)）
将点排序，先按从下到上，y坐标相等再按从左到右，排序后，正着遍历一遍找到最低点到最高点满足（即右边部分的凸包）， 反着遍历一遍找到最高点到最低点满足（即左边部分的凸包） 注意：算个数的时候，算法对于最低点和最高点都算了两次，同时要考虑是否要共线。
#include <cstdio> #include <cmath> #include <algorithm> using namespace std; /* poj 1113 题意：要求建一堵围墙围绕城堡，墙于城堡的距离不小于L，输入城堡每个节点的坐标，求围墙的最小长度。 题解：凸包加上360°的弧长。 */ const int N = 1010; const double PI = acos(-1.0); struct Point { double x,y; }; bool cmp(Point aa,Point bb) { if(aa.y != bb.y) return aa.y < bb.y; return aa.x < bb.x; } //是否严格左转，共线不算（叉乘） double xmult(Point a,Point b,Point c) //(ca)×(cb) { return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); } Point a[N]; int n,cnt,tail; int tmp[N],ans[N]; void Jarvis() { sort(a,a+n,cmp); cnt = tail = 0; tmp[tail++] = 0; tmp[tail++] = 1; for(int i = 2; i < n; i++) { while(tail>1 && xmult(a[tmp[tail-1]],a[i],a[tmp[tail-2]])<=0) tail--; tmp[tail++] = i; } for(int i = 0; i < tail; i++) ans[cnt++] = tmp[i]; tail = 0; tmp[tail++] = n-1; tmp[tail++] = n-2; for(int i = n-3; i >= 0; i--) { while(tail>1 && xmult(a[tmp[tail-1]],a[i],a[tmp[tail-2]])<=0) tail--; tmp[tail++] = i; } for(int i = 0; i < tail; i++) ans[cnt++] = tmp[i]; } double dist(Point p1,Point p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y)); } int main() { double L; while(~scanf("%d%lf",&n,&L)) { for(int i = 0; i < n; i++) scanf("%lf%lf",&a[i].x,&a[i].y); Jarvis(); double res = 2*PI*L; for(int i = 0; i < cnt-1; i++) res += dist(a[ans[i]],a[ans[i+1]]); printf("%.0f\n",res); } return 0; }