POJ 3347 - Kadj Squares

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

概要

n 個の異なる大きさの正方形 S[1], ..., S[n] があり，それぞれの一辺の長さ s[i] が与えられる．

これらを xy 平面上に，x 軸および y 軸と45度の角度をなすようにして x 軸上に y = 0 から順に並べていく．

つまり，S[i] の y 軸上にある頂点の x 座標を b[i] とすると，

という条件を満たすように並べる．

このとき，上から見える正方形をすべて答える． ここで「S[i] が上から見える」とは，S[i] の内部のある点 p から上に半直線を伸ばしたとき，S[i] 以外の正方形と交わらないこととする．

制約

解法

まず b[i] を求める． おそらく場合分けしつつ何らかの計算式で求まると思うが，面倒そうだったので二分探索で S[i] をできるだけ左でかつ S[1], ..., S[i-1] と重ならないような点を求めた．

b[i] を求めてしまえば，b[i]±s[i]/sqrt(2) の範囲で S[i] 以外の図形と交わらないような範囲があるかどうかチェックすれば，上から見えるかどうかわかる．

 1 #include <iostream>
 2 #include <vector>
 3 #include <iterator>
 4 #include <cmath>
 5 using namespace std;
 6 static const double SQRT2 = sqrt(2.0);
 7 static const double EPS = 1e-6;
 8 
 9 bool ok(const vector<int>& s, const vector<double>& b, int k, double p)
10 {
11   const double y = s[k]/SQRT2;
12   const double x = p - y;
13   for (int i = 0; i < k; i++) {
14     if (x-b[i] <= y && y <= -x+b[i]+SQRT2*s[i]) {
15       return false;
16     }
17   }
18   return true;
19 }
20 
21 int main()
22 {
23   int N;
24   while (cin >> N && N != 0) {
25     vector<int> s(N);
26     for (int i = 0; i < N; i++) {
27       cin >> s[i];
28     }
29     vector<double> b(N);
30     b[0] = s[0] / SQRT2;
31     for (int i = 1; i < N; i++) {
32       double left = max(b[i-1], s[i]/SQRT2), right = 1e5;
33       for (int j = 0; j < 100; j++) {
34         const double mid = (left + right)/2.0;
35         if (ok(s, b, i, mid)) {
36           right = mid;
37         } else {
38           left = mid;
39         }
40       }
41       b[i] = (left + right)/2.0;
42     }
43 
44     bool first = true;
45     for (int i = 0; i < N; i++) {
46       double l = b[i] - s[i]/SQRT2;
47       double r = b[i] + s[i]/SQRT2;
48       for (int j = 0; j < N; j++) {
49         if (j < i) {
50           l = max(l, b[j] + s[j]/SQRT2);
51         } else if (i < j) {
52           r = min(r, b[j] - s[j]/SQRT2);
53         }
54       }
55       if (r - l > EPS) {
56         if (!first) {
57           cout << " ";
58         }
59         first = false;
60         cout << i+1;
61       }
62     }
63     cout << endl;
64   }
65   return 0;
66 }
poj/3347.cc