hdu 1348 Wall （Convex Hull）

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

　　简单二维凸包，直接套用andrew算法得到凸包后求周长，然后加上一个圆周即可。

　　做的过程中有一个小错误，就是之前已经cin >> n;了，做凸包的时候写成了int n = andrew(pt, n, ch); 从而导致segment fault。以后要注意避免这样的事再次发生。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <iostream>
 7 
 8 using namespace std;
 9 
10 struct Point {
11     double x, y;
12     Point() { x = y = 0.0;}
13     Point(double x, double y) : x(x), y(y) {}
14 } ;
15 template <class T> T sqr(T x) { return x * x;}
16 inline double ptDis(Point a, Point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
17 
18 typedef Point Vec;
19 Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
20 Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
21 Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
22 Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
23 
24 const double EPS = 1e-8;
25 const double PI = acos(-1.0);
26 inline int sgn(double x) { return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1);}
27 bool operator < (Point a, Point b) { return a.x < b.x || a.x == b.x && a.y < b.y;}
28 bool operator == (Point a, Point b) { return !sgn(a.x - b.x) && !sgn(a.y - b.y);}
29 
30 inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
31 inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
32 inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
33 inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
34 
35 struct Line {
36     Point s, t;
37     Line() {}
38     Line(Point s, Point t) : s(s), t(t) {}
39 } ;
40 
41 int andrew(Point *pt, int n, Point *ch) {
42 //    cout << "sort!!" << n << endl;
43     sort(pt, pt + n);
44     int m = 0;
45 //    cout << "here??" << endl;
46     for (int i = 0; i < n; i++) {
47         while (m > 1 && crossDet(ch[m - 2], ch[m - 1], pt[i]) <= 0) m--;
48         ch[m++] = pt[i];
49     }
50     int k = m;
51     for (int i = n - 2; i >= 0; i--) {
52         while (m > k && crossDet(ch[m - 2], ch[m - 1], pt[i]) <= 0) m--;
53         ch[m++] = pt[i];
54     }
55     if (n > 1) m--;
56     return m;
57 }
58 
59 const int N = 1111;
60 Point pt[N], ch[N];
61 
62 int main() {
63 //    freopen("in", "r", stdin);
64     int T, n;
65     double r;
66     cin >> T;
67     while (T--) {
68         cin >> n >> r;
69 //        cout << n << ' ' << r << endl;
70         for (int i = 0; i < n; i++) {
71             cin >> pt[i].x >> pt[i].y;
72         }
73 //        cout << "read?" << n << endl;
74         n = andrew(pt, n, ch);
75         ch[n] = ch[0];
76         double sum = 0.0;
77         for (int i = 0; i < n; i++) {
78             sum += ptDis(ch[i], ch[i + 1]);
79         }
80         printf("%.0f\n", sum + 2.0 * PI * r);
81         if (T) cout << endl;
82     }
83     return 0;
84 }

View Code

——written by Lyon