POJ 2165 - Gunman

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

概要

3次元空間に \(n\) 枚の長方形の窓がある。 どの窓も各辺は X 座標あるいは Y 座標に並行であり、Z 座標はすべて異なる。

X 軸上の好きな位置から、一直線に進む銃弾を撃つことができる。 このときすべての窓を貫けるかどうかを答え、貫ける場合は X 軸上の位置と銃弾と各窓との交点を答える。

制約

解法

の両方にギリギリ当たるような直線を考えると、gunman の位置は一意に定まり、直線も定まるのですべての窓と交わるかどうか判定できる。 あとはこれの全通りの組み合わせを試せばよい。

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 static const double EPS = 1e-8;
 5 
 6 struct P3 { double x, y, z; };
 7 
 8 struct window
 9 {
10   int ps[4], z;
11   int x1() const { return ps[0]; }
12   int y1() const { return ps[1]; }
13   int x2() const { return ps[2]; }
14   int y2() const { return ps[3]; }
15 };
16 
17 bool check(const vector<window>& v, int x1, int y1, int z1, int x2, int z2, double& a, vector<P3>& ans)
18 {
19   const double dx = double(x2 - x1)/double(z2 - z1);
20   a = x1 + dx*(-z1);
21   double dy = double(y1 - 0)/double(z1);
22   const int N = v.size();
23   for (int i = 0; i < N; i++) {
24     const double x = a + dx*(v[i].z);
25     const double y = 0 + dy*(v[i].z);
26     ans[i].x = x;
27     ans[i].y = y;
28     ans[i].z = v[i].z;
29     if (x < v[i].x1() - EPS || v[i].x2() < x - EPS || y < v[i].y1() - EPS || v[i].y2() < y - EPS) {
30       return false;
31     }
32   }
33   return true;
34 }
35 
36 int main()
37 {
38   int N;
39   scanf("%d", &N);
40   vector<window> v(N);
41   for (int i = 0; i < N; i++) {
42     scanf("%d %d %d %d %d", &v[i].ps[0], &v[i].ps[1], &v[i].ps[2], &v[i].ps[3], &v[i].z);
43   }
44 
45   vector<P3> ans(N);
46   for (int i = 0; i < N; i++) {
47     for (int j = 0; j < 4; j++) {
48       static const int tbl[4][2] = {
49         {0, 1}, {0, 3}, {2, 1}, {2, 3},
50       };
51       const int x1 = v[i].ps[tbl[j][0]], y1 = v[i].ps[tbl[j][1]], z1 = v[i].z;
52       for (int k = 0; k < N; k++) {
53         if (i == k) {
54           continue;
55         }
56         for (int l = 0; l < 2; l++) {
57           double x;
58           if (check(v, x1, y1, z1, v[k].ps[2*l], v[k].z, x, ans)) {
59             puts("SOLUTION");
60             printf("%.6f\n", x);
61             for (vector<P3>::const_iterator it = ans.begin(); it != ans.end(); ++it) {
62               printf("%.6f %.6f %.6f\n", it->x, it->y, it->z);
63             }
64             return 0;
65           }
66         }
67       }
68     }
69   }
70   puts("UNSOLVABLE");
71   return 0;
72 }
poj/2165.cc