【凸包Graham_Scan算法】HDU 1348 Wall
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, ch;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//找相对于p的极角，并把除了p以外的点按照极角排序for (i = 1; i < n; i++)p.angel = atan2 (p.y-p.y, p.x-p.x);sort (p+1, p+n, cmp2);//Graham_Scan算法ch = p, ch = p, ch = p;top = 3;for (i = 3; i < n; i++){while (top > 2 && multi (ch, ch, p) <= 0)top--;ch = p;}//求周长len = dist (ch, ch);for (i = 1; i < top; i++)len += dist (ch, ch);len += 2 * PI * r; //加上圆弧，刚好为一个圆！printf ("%.0lf\n", len);if (t)printf ("\n");}return 0;}
页:
[1]