【HDOJ】1348 Wall

计算几何-凸包模板题目，Graham算法解。
 1 /* 1348 */
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <algorithm>
 8 using namespace std;
 9 
10 #define MAXN 1005
11 
12 typedef struct Point_t {
13     double x, y;
14     Point_t() {}
15     Point_t(double xx, double yy) {
16         x = xx; y = yy;
17     }
18 } Point_t;
19 
20 Point_t stack[MAXN];
21 Point_t points[MAXN];
22 const double PI = acos(-1.0);
23 int n;
24 
25 double Length(Point_t a, Point_t b) {
26     return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
27 }
28 
29 double cross(Point_t p0, Point_t p1, Point_t p2) {
30     return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
31 }
32 
33 bool comp(Point_t a, Point_t b) {
34     double k = cross(points[0], a, b);
35     return !(k<0 || (k==0 && Length(points[0], a)>Length(points[0], b)));
36 }
37 
38 double Graham() {
39     double ret = 0;
40     int i, j, k;
41     int top;
42     Point_t p0;
43     
44     p0 = points[0];
45     k = 0;
46     for (i=1; i<n; ++i) {
47         if (points[i].x<p0.x || (points[i].x==p0.x && points[i].y<p0.y)) {
48             p0 = points[i];
49             k = i;
50         }
51     }
52     
53     points[k] = points[0];
54     points[0] = p0;
55     sort(points+1, points+n, comp);
56     
57     stack[0] = points[0];
58     stack[1] = points[1];
59     stack[2] = points[2];
60     top = 2;
61     for (i=3; i<n; ++i) {
62         while (cross(stack[top-1], stack[top], points[i])<=0 && top>1)
63             --top;
64         stack[++top] = points[i];
65     }
66     stack[++top] = p0;
67     for (i=1; i<=top; ++i)
68         ret += Length(stack[i-1], stack[i]);
69     
70     return ret;
71 }
72 
73 int main() {
74     int t;
75     int i, j, k, tmp;
76     double l, ans;
77     
78     #ifndef ONLINE_JUDGE
79         freopen("data.in", "r", stdin);
80     #endif
81     
82     scanf("%d", &t);
83     while (t--) {
84         scanf("%d %lf", &n, &l);
85         for (i=0; i<n; ++i)
86             scanf("%lf %lf", &points[i].x, &points[i].y);
87         ans = Graham();
88         ans += PI * (l+l);
89         printf("%.0lf
", ans);
90         if (t)
91             printf("
");
92     }
93     
94     return 0;
95 }