POJ 1113 - Wall

http://poj.org/problem?id=1113

概要

N 個の点からなる城の形が与えらる． 城の周りから L 以上離れた場所に壁を作る． このときに必要な壁の長さの合計の最小値を答える．

制約

解法

まず凸包を求めて，各辺について，辺と同じ長さの壁を L だけ離して作る． そしてそれらを，頂点を中心とした半径 L の弧で壁を繋げば最小となる．

はじめ，各頂点について角度を求めて弧の長さを計算して足していくように実装したが， 外角の和は 2π になるので，辺の長さの和に 2πL を足すだけでよかった．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <complex>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 typedef complex<double> P;
 8 static const double EPS = 1e-6;
 9 static const double PI = acos(-1.0);
10 namespace std {
11   bool operator<(const P& p, const P& q)
12   {
13     return abs(p.real() - q.real()) < EPS ? p.imag() < q.imag() : p.real() < q.real();
14   }
15 };
16 
17 inline double dot(const P& a, const P& b)
18 {
19   return a.real()*b.real() + a.imag()*b.imag();
20 }
21 
22 inline double cross(const P& a, const P& b)
23 {
24   return a.real()*b.imag() - b.real()*a.imag();
25 }
26 
27 inline int ccw(P a, P b, P c) {/*{{{*/
28   b -= a; c -= a;
29   if (cross(b, c) > 0) {
30     return 1; // counter clockwise
31   } else if (cross(b, c) < 0) {
32     return -1;  // clockwise
33   } else if (dot(b, c) < 0) {
34     return 2; // c-a-b on line
35   } else if (abs(b) < abs(c)) {
36     return -2;  // a-b-c on line
37   }
38   return 0;
39 }/*}}}*/
40 
41 vector<P> convex(const vector<P>& ps)/*{{{*/
42 {
43   const int N = ps.size();
44   vector<P> ch(2*N);
45   int k = 0;
46   // upper
47   for (int i = 0; i < N; i++) {
48     while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) {
49       k--;
50     }
51     ch[k] = ps[i];
52     k++;
53   }
54   // lower
55   for (int i = N-2, t = k+1; i >= 0; i--) {
56     while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) {
57       k--;
58     }
59     ch[k] = ps[i];
60     k++;
61   }
62   ch.resize(k-1);
63   return ch;
64 }/*}}}*/
65 
66 int main()
67 {
68   int N, L;
69   scanf("%d %d", &N, &L);
70   vector<P> ps;
71   for (int i = 0; i < N; i++) {
72     double x, y;
73     scanf("%lf %lf", &x, &y);
74     ps.push_back(P(x, y));
75   }
76   sort(ps.begin(), ps.end());
77 
78   const vector<P> qs = convex(ps);
79   const int M = qs.size();
80   double ans = 2*L*PI;
81   for (int i = 0; i < M; i++) {
82     ans += abs(qs[(i+1)%M] - qs[i]);
83   }
84   printf("%ld\n", lround(ans));
85 
86   return 0;
87 }
poj/1113.cc