POJ 1819 - Disks

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

概要

N 個の円盤が与えられ，i 番目の円盤は半径 r[i] である．

円盤を与えられた順に x 軸上に並べていく． i 番目の円盤は y 軸か別の円盤と接するまでできるだけ -x 方向に置く．

「その円盤を取り除いても，全体の幅が変わらない」ような円盤を dispensable と呼ぶ． このとき，dispensable な円盤の数とそれらのインデックスをを全て答える．

制約

• N <= 1000

解法

dispensable な円盤は，

• i 番目と j 番目 (i < j) の円盤が接しているとき，i < k < j なる k 番目の円盤
• 最も +x 方向に伸びている円盤が r 番目だったとすると，r < k なる k 番目の円盤

に限る．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <cmath>
 4 using namespace std;
 5 static const double EPS = 1e-8;
 6 
 7 int main()
 8 {
 9   int N;
10   scanf("%d", &N);
11   vector<double> rs(N);
12   for (int i = 0; i < N; i++) {
13     scanf("%lf", &rs[i]);
14   }
15 
16   vector<double> xs(rs);
17   vector<bool> dispensable(N, false);
18   double right = 2.0*rs[0];
19   int ridx = 0;
20   for (int i = 1; i < N; i++) {
21     int k = -1;
22     for (int j = 0; j < i; j++) {
23       const double d = 2.0*sqrt(rs[i]*rs[j]) + xs[j];
24       if (xs[i] - d < EPS) {
25         xs[i] = d;
26         k = j;
27       }
28     }
29     for (int j = k+1; j < i; j++) {
30       dispensable[j] = true;
31     }
32 
33     if (right - (xs[i] + rs[i]) < EPS) {
34       right = xs[i] + rs[i];
35       ridx = i;
36     }
37   }
38 
39   for (int i = ridx+1; i < N; i++) {
40     dispensable[i] = true;
41   }
42 
43   int K = 0;
44   for (int i = 0; i < N; i++) {
45     if (dispensable[i]) {
46       ++K;
47     }
48   }
49   printf("%d\n", K);
50   for (int i = 0; i < N; i++) {
51     if (dispensable[i]) {
52       printf("%d\n", i+1);
53     }
54   }
55   return 0;
56 }