LightOJ 1239 Convex Fence (Convex Hull)

Jan's LightOJ :: Problem 1239 - Convex Fence
　　简单凸包，练手题。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <iostream>
 7 
 8 using namespace std;
 9 
10 typedef long long LL;
11 
12 struct Point {
13     LL x, y;
14     Point() {}
15     Point(LL x, LL y) : x(x), y(y) {}
16 } ;
17 
18 bool operator < (Point x, Point y) { return x.x < y.x || (x.x == y.x && x.y < y.y);}
19 Point operator - (Point x, Point y) { return Point(x.x - y.x, x.y - y.y);}
20 
21 inline LL crossDet(Point a, Point b) { return a.x * b.y - a.y * b.x;}
22 inline LL crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
23 
24 int andrew(Point *pt, int n, Point *ch) {
25     sort(pt, pt + n);
26     int m = 0;
27     for (int i = 0; i < n; i++) {
28         while (m > 1 && crossDet(ch[m - 2], ch[m - 1], pt[i]) <= 0) m--;
29         ch[m++] = pt[i];
30     }
31     int k = m;
32     for (int i = n - 2; i >= 0; i--) {
33         while (m > k && crossDet(ch[m - 2], ch[m - 1], pt[i]) <= 0) m--;
34         ch[m++] = pt[i];
35     }
36     if (m > 1) m--;
37     return m;
38 }
39 
40 template <class T> T sqr(T x) { return x * x;}
41 
42 double ptDis(Point x, Point y) {
43     double dx = x.x - y.x;
44     double dy = x.y - y.y;
45     return sqrt(sqr(dx) + sqr(dy));
46 }
47 
48 const double PI = acos(-1.0);
49 const int N = 55555;
50 Point pt[N], ch[N];
51 
52 int main() {
53 //    freopen("in", "r", stdin);
54     int n, d, T;
55     cin >> T;
56     for (int cas = 1; cas <= T; cas++) {
57         cin >> n >> d;
58         for (int i = 0; i < n; i++) {
59             scanf("%lld%lld", &pt[i].x, &pt[i].y);
60         }
61         n = andrew(pt, n, ch);
62         ch[n] = ch[0];
63         double sum = 0.0;
64         for (int i = 0; i < n; i++) {
65             sum += ptDis(ch[i], ch[i + 1]);
66         }
67         printf("Case %d: %.9f\n", cas, sum + 2.0 * PI * d);
68     }
69     return 0;
70 }
View Code
——written by Lyon