【凸包Graham_Scan算法】HDU 1348 Wall

基德KID.1412

http://acm.hdu.edu.cn/showproblem.php?pid=1348

典型凸包题，求外围城墙的周长
Sample Input
1
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200

Sample Output
1628

#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <ctype.h>using namespace std;#define PI 3.14159265struct point{double x, y, angel;}p[1005], ch[1005];double dist (point a, point b){return sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));}double multi (point a, point b, point c){double x1, y1, x2, y2;x1 = b.x - a.x;y1 = b.y - a.y;x2 = c.x - b.x;y2 = c.y - b.y;return x1*y2 - x2*y1;}bool cmp (point a, point b){if (a.y == b.y)return a.x < b.x;return a.y < b.y;}bool cmp2 (point a, point b){if (a.angel == b.angel){if (a.x == b.x)return a.y > b.y;return a.x > b.x;}return a.angel < b.angel;}int main(){int n, i, top, t;double r, len;scanf ("%d", &t);while (t--){scanf ("%d%lf", &n, &r);for (i = 0; i < n; i++)scanf ("%lf%lf", &p.x, &p.y);sort (p, p+n, cmp);    //找到左下角的p[0]//找相对于p[0]的极角，并把除了p[0]以外的点按照极角排序for (i = 1; i < n; i++)p.angel = atan2 (p.y-p[0].y, p.x-p[0].x);sort (p+1, p+n, cmp2);//Graham_Scan算法ch[0] = p[0], ch[1] = p[1], ch[2] = p[2];top = 3;for (i = 3; i < n; i++){while (top > 2 && multi (ch[top-2], ch[top-1], p) <= 0)top--;ch[top++] = p;}//求周长len = dist (ch[0], ch[top-1]);for (i = 1; i < top; i++)len += dist (ch, ch[i-1]);len += 2 * PI * r;    //加上圆弧，刚好为一个圆！printf ("%.0lf\n", len);if (t)printf ("\n");}return 0;}