题目大意：
给定多边形城堡的n个顶点，绕城堡外面建一个围墙，围住所有点，并且墙与所有点的距离至少为L，求这个墙最小的长度
思路：
结果等于凸包周长 + 一个完整圆的周长。
当绕城堡外面走一圈，在拐角处所形成的弧度相加为一个长度为Ｌ的圆。
1 /* 2 poj 1113 3 凸包 4 大意： 5 给定多边形城堡的n个顶点，绕城堡外面建一个围墙，围住所有点， 6 并且墙与所有点的距离至少为L，求这个墙最小的长度 7 */ 8 9 #include <iostream> 10 #include <math.h> 11 #include <cstring> 12 #include <algorithm> 13 #include <stdlib.h> 14 15 using namespace std; 16 #define pi acos(-1.0) 17 #define eps 1e-8 18 #define zero(x) (((x)>0?(x):-(x))<eps) 19 20 struct point 21 { 22 double x, y; 23 }p[1005], convex[1005]; 24 25 //两点间距离 26 double dis(point a, point b) 27 { 28 return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y) * (a.y - b.y)); 29 } 30 31 //计算cross product (P1-P0)x(P2-P0) 32 //叉积 33 double xmult(point p1, point p2, point p0) 34 { 35 return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y); 36 } 37 //graham算法顺时针构造包含所有共线点的凸包,O(nlogn) 38 point p1, p2; 39 40 int graham_cp(const void* a, const void* b) 41 { 42 double ret = xmult(*((point*) a), *((point*) b), p1); 43 double ret2 = xmult(*((point*) a), *((point*) b), p2); 44 return zero(ret) ? (ret2> 0 ? 1 : -1) : (ret > 0 ? 1 : -1); 45 } 46 47 void _graham(int n, point* p, int& s, point* ch) 48 { 49 int i, k = 0; 50 for (p1 = p2 = p[0], i = 1; i<n; p2.x += p[i].x, p2.y += p[i].y, i++) 51 if (p1.y - p[i].y>eps || (zero(p1.y - p[i].y) && p1.x > p[i].x)) 52 p1 = p[k = i]; 53 p2.x /= n, p2.y /= n; 54 p[k] = p[0], p[0] = p1; 55 qsort(p + 1, n - 1, sizeof(point), graham_cp); 56 for (ch[0] = p[0], ch[1] = p[1], ch[2] = p[2], s = i = 3; i < n; ch[s++] = p[i++]) 57 for (; s>2 && xmult(ch[s - 2], p[i], ch[s - 1]) < -eps; s--); 58 } 59 60 int wipesame_cp(const void *a, const void *b) 61 { 62 if ((*(point *) a).y < (*(point *) b).y - eps) return -1; 63 else if ((*(point *) a).y > (*(point *) b).y + eps) return 1; 64 else if ((*(point *) a).x < (*(point *) b).x - eps) return -1; 65 else if ((*(point *) a).x > (*(point *) b).x + eps) return 1; 66 else return 0; 67 } 68 69 int _wipesame(point * p, int n) 70 { 71 int i, k; 72 qsort(p, n, sizeof(point), wipesame_cp); 73 for (k = i = 1; i < n; i++) 74 if (wipesame_cp(p + i, p + i - 1) != 0) p[k++] = p[i]; 75 return k; 76 } 77 78 //构造凸包接口函数,传入原始点集大小n,点集p(p原有顺序被打乱!) 79 //返回凸包大小,凸包的点在convex中 80 //参数maxsize为1包含共线点,为0不包含共线点,缺省为1 81 //参数dir为1顺时针构造,为0逆时针构造,缺省为1 82 //在输入仅有若干共线点时算法不稳定,可能有此类情况请另行处理! 83 int graham(int n, point* p, point* convex, int maxsize = 1, int dir = 1) 84 { 85 point* temp = new point[n]; 86 int s, i; 87 n = _wipesame(p, n); 88 _graham(n, p, s, temp); 89 for (convex[0] = temp[0], n = 1, i = (dir ? 1 : (s - 1)); dir ? (i < s) : i; i += (dir ? 1 : -1)) 90 if (maxsize || !zero(xmult(temp[i - 1], temp[i], temp[(i + 1)%s]))) 91 convex[n++] = temp[i]; 92 delete []temp; 93 return n; 94 } 95 96 int main() 97 { 98 int n; 99 double d; 100 while (cin >> n >> d) 101 { 102 memset(p,0,sizeof(p)); 103 memset(convex, 0, sizeof(convex)); 104 double dist = 0.0; 105 for (int i = 0; i < n; i++) 106 { 107 cin >> p[i].x >> p[i].y; 108 } 109 //cout << n << endl; 110 int size = graham(n, p, convex,0); 111 // cout << size << endl; 112 for (int i = 0; i < size - 1; i++) 113 { 114 dist += dis(convex[i], convex[i + 1]); 115 } 116 dist += dis(convex[size - 1], convex[0]);//别忘了起始到结束的长度 117 cout << (int) (dist + 2 * pi * d + 0.5) << endl; 118 } 119 }