POJ 1873 - The Fortified Forest

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

概要

n 本の木があり，i 番目の木を切ると v[i] の損失を被る代わりに l[i] の長さのフェンスを作ることができる．

損失を最小にしつつ，切られていないすべての木を囲むことができるフェンスを作ったとき，切る必要のある木と そのときにできたフェンスが必要な長さよりどれくらい長かったかを答える．

ただし，損失が最小になるような切り方が複数ある場合，切る本数が少ないほうを答える．

制約

解法

切り方を全通り試す． 残った木を囲むフェンスの長さは，凸包を求めてその周の長さで求める．

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <complex>
 4 using namespace std;
 5 typedef complex<double> P;
 6 static const double EPS = 1e-6;
 7 namespace std {
 8   bool operator<(const P& p, const P& q)
 9   {
10     return abs(p.real() - q.real()) < EPS ? p.imag() < q.imag() : p.real() < q.real();
11   }
12 };
13 
14 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
15 
16 double convex_len(const P *ps, int N)/* {{{*/
17 {
18   static P ch[40];
19   int k = 0;
20   for (int i = 0; i < N; i++) {
21     while (k >= 2 && cross(ch[k-1]-ch[k-2], ps[i]-ch[k-2]) <= EPS) {
22       k--;
23     }
24     ch[k] = ps[i];
25     k++;
26   }
27   for (int i = N-2, t = k+1; i >= 0; i--) {
28     while (k >= t && cross(ch[k-1]-ch[k-2], ps[i]-ch[k-2]) <= EPS) {
29       k--;
30     }
31     ch[k] = ps[i];
32     k++;
33   }
34   const int K = k-1;
35   double l = 0.0;
36   for (int i = 0; i < K; i++) {
37     l += abs(ch[i] - ch[(i+1)%K]);
38   }
39   return l;
40 }/*}}}*/
41 
42 int main()
43 {
44   int N;
45   for (int Ti = 1; scanf("%d", &N) != EOF && N != 0; Ti++) {
46     static P ps[20];
47     static int vs[20], ls[20];
48     for (int i = 0; i < N; i++) {
49       int x, y;
50       scanf("%d %d %d %d", &x, &y, &vs[i], &ls[i]);
51       ps[i] = P(x, y);
52     }
53 
54     int ans;
55     int min_lost = 10000000;
56     double extra;
57     for (int s = 1; s < (1<<N); s++) {
58       static P qs[20];
59       int lost = 0, len = 0, size = 0;
60       for (int i = 0; i < N; i++) {
61         if (s & (1<<i)) {
62           qs[size++] = ps[i];
63         } else {
64           len += ls[i];
65           lost += vs[i];
66         }
67       }
68       if (lost > min_lost) {
69         continue;
70       }
71       sort(qs, qs+size);
72       const double l = convex_len(qs, size);
73       if (l <= len) {
74         if (lost < min_lost || (lost == min_lost  && __builtin_popcount(~s) < __builtin_popcount(ans))) {
75           min_lost = lost;
76           ans = ~s;
77           extra = len - l;
78         }
79       }
80     }
81 
82     printf("Forest %d\n", Ti);
83     printf("Cut these trees:");
84     for (int i = 0; i < N; i++) {
85       if (ans & (1<<i)) {
86         printf(" %d", i+1);
87       }
88     }
89     putchar('\n');
90     printf("Extra wood: %.2f\n\n", extra);
91   }
92   return 0;
93 }
poj/1873.cc