hdu 1392 Surround the Trees (Convex Hull + Trick)

http://acm.hdu.edu.cn/showproblem.php?pid=1392
　　模板题，套二维凸包，然后计算凸包周长。
　　唯一要注意的是两个点的时候，不用两点距离的两倍。
代码如下：
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <set>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 
 9 using namespace std;
10 
11 struct Point {
12     double x, y;
13     Point() {}
14     Point(double x, double y) : x(x), y(y) {}
15 } ;
16 template <class T> inline T sqr(T x) { return x * x;}
17 inline double ptDis(Point a, Point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
18 
19 typedef Point Vec;
20 Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
21 Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
22 Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
23 Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
24 
25 const double EPS = 1e-8;
26 const double PI = acos(-1.0);
27 inline int sgn(double x) { return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1);}
28 bool operator < (Point a, Point b) { return a.x < b.x || a.x == b.x && a.y < b.y;}
29 bool operator == (Point a, Point b) { return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;}
30 
31 inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
32 inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
33 inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
34 inline double vecLen(Vec x) { return sqrt(sqr(x.x) + sqr(x.y));}
35 
36 struct Line {
37     Point s, t;
38     Line() {}
39     Line(Point s, Point t) : s(s), t(t) {}
40     Point point(double x) {
41         return s + (t - s) * x;
42     }
43     Vec vec() { return t - s;}
44 } ;
45 typedef Line Seg;
46 
47 int andrew(Point *pt, int n, Point *ch) {
48     sort(pt, pt + n);
49     int m = 0;
50     for (int i = 0; i < n; i++) {
51         while (m > 1 && crossDet(ch[m - 1] - ch[m - 2], pt[i] - ch[m - 2]) <= 0.0) m--;
52         ch[m++] = pt[i];
53     }
54     int k = m;
55     for (int i = n - 2; i >= 0; i--) {
56         while (m > k && crossDet(ch[m - 1] - ch[m - 2], pt[i] - ch[m - 2]) <= 0.0) m--;
57         ch[m++] = pt[i];
58     }
59     if (n > 1) m--;
60     return m;
61 }
62 
63 int main() {
64 //    freopen("in", "r", stdin);
65     int n;
66     Point p[1111], c[1111];
67     while (cin >> n && n) {
68         for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
69         int m = andrew(p, n, c);
70         double ans = 0;
71         c[m] = c[0];
72         for (int i = 0; i < m; i++) {
73 //            cout << c[i].x << ' ' << c[i].y << endl;
74             ans += ptDis(c[i], c[i + 1]);
75         }
76         printf("%.2f\n", m == 2 ? ans / 2.0 : ans);
77     }
78     return 0;
79 }
View Code
——written by Lyon