POJ 2160 - Box

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

概要

与えられた6つの長方形から直方体が作れるかどうかを答える．

制約

解法

やるだけ．

まずちゃんとペアが作れるかどうか確認し，縦横を入れ替えつつ全組み方を試した．

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 bool ok(const pair<int,int> *rects)
 6 {
 7   if (rects[0] != rects[1]) {
 8     return false;
 9   }
10   if (rects[2] != rects[3]) {
11     return false;
12   }
13   if (rects[4] != rects[5]) {
14     return false;
15   }
16 
17   for (int s = 0; s < (1<<3); s++) {
18     pair<int,int> r[3];
19     for (int i = 0; i < 3; i++) {
20       r[i] = rects[2*i];
21       if (s & (1<<i)) {
22         swap(r[i].first, r[i].second);
23       }
24     }
25     sort(r, r+3);
26     do {
27       if (r[0].first == r[1].first
28           && r[1].second == r[2].second
29           && r[2].first == r[0].second) {
30         return true;
31       }
32     } while (next_permutation(r, r+3));
33   }
34   return false;
35 }
36 
37 int main()
38 {
39   pair<int,int> rects[6];
40   for (int i = 0; i < 6; i++) {
41     int w, h;
42     cin >> w >> h;
43     if (w > h) {
44       swap(w, h);
45     }
46     // w <= h
47     rects[i].first = w;
48     rects[i].second = h;
49   }
50   sort(rects, rects+6);
51   cout << (ok(rects) ? "POSSIBLE" : "IMPOSSIBLE") << endl;
52   return 0;
53 }
poj/2160.cc