题目来源：http://poj.org/problem?id=1022
题目大意：
有一些4维的单位体积的立方体盒子，每个立方体有8个面。要用一个大的4为盒子将它们包起来，求最小的大盒子体积。
输入：第一行为测试用例数。每个用例的第一行为单位立方体数目n。接下来的n行每行为一个立方体的信息。每行第一个数字为还立方体的编号，接下来的8个整数分别为对应面相邻的立方体的编号。该面没有邻居则为0.（给出的都是单一刚体。）
输出：最小的能把这个由小4D立方体拼起来的形状的盒子的体积。
Sample Input
1
9
1 2 3 4 5 6 7 8 9
2 0 1 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0
4 0 0 0 1 0 0 0 0
5 0 0 1 0 0 0 0 0
6 0 0 0 0 0 1 0 0
7 0 0 0 0 1 0 0 0
8 0 0 0 0 0 0 0 1
9 0 0 0 0 0 0 1 0
Sample Output
81
本题题干描述得很复杂，想象起来也有一些抽象，其实很简单，跟3D的情况联系起来想就可以了。3D求包围盒的方法推广至4D即可。
//////////////////////////////////////////////////////////////////////////
// POJ1022 Packing Unit 4D Cubes
// Memory: 300K Time: 16MS
// Language: C++ Result: Accepted
////////////////////////////////////////////////////////////////////////// #include <iostream>
#include <vector>
#include <map> using namespace std; class Cube {
public:
int x1p, x1n, x2p, x2n, x3p, x3n, x4p, x4n;
};
class Pos {
public:
int id;
int x1, x2, x3, x4;
}; int main() {
int ncase;
cin >> ncase;
for (int caseNo = ; caseNo <= ncase; ++caseNo) {
int n;
map<int, Cube> cubes;
cin >> n;
for (int i = ; i <= n; ++i) {
int id;
cin >> id;
Cube cube;
cin >> cube.x1p >> cube.x1n >> cube.x2p >> cube.x2n
>> cube.x3p >> cube.x3n >> cube.x4p >> cube.x4n;
cubes[id] = cube;
}
bool ok = true;
vector<Pos> solid;
Pos firstPos;
firstPos.id = (*cubes.begin()).first;
firstPos.x1 = firstPos.x2 = firstPos.x3 = firstPos.x4 = ;
solid.push_back(firstPos);
for (map<int, Cube>::iterator itc = cubes.begin(); itc != cubes.end(); ++itc) {
Cube cube1;
int id = (*itc).first;
int x1p = (*itc).second.x1p;
//x1p
if (x1p != ) {
if (cubes[x1p].x1n != id) {
ok = false;
break;
}
bool f = true;
Pos pos;
for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
if (f == false) break;
if ((*its).id == id) {
pos.id = x1p;
pos.x1 = (*its).x1 + ;
pos.x2 = (*its).x2;
pos.x3 = (*its).x3;
pos.x4 = (*its).x4;
for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
if ((*itr).id == x1p) {
f = false;
break;
}
}
}
}
if (f == true) {
solid.push_back(pos);
}
} //x1n
int x1n = (*itc).second.x1n;
if (x1n != ) {
if (cubes[x1n].x1p != id) {
ok = false;
break;
}
bool f = true;
Pos pos;
for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
if (f == false) break;
if ((*its).id == id) {
pos.id = x1n;
pos.x1 = (*its).x1 - ;
pos.x2 = (*its).x2;
pos.x3 = (*its).x3;
pos.x4 = (*its).x4;
for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
if ((*itr).id == x1n) {
f = false;
break;
}
}
}
}
if (f == true) {
solid.push_back(pos);
}
} //x2p
int x2p = (*itc).second.x2p;
if (x2p != ) {
if (cubes[x2p].x2n != id) {
ok = false;
break;
}
bool f = true;
Pos pos;
for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
if (f == false) break;
if ((*its).id == id) {
pos.id = x2p;
pos.x1 = (*its).x1;
pos.x2 = (*its).x2 + ;
pos.x3 = (*its).x3;
pos.x4 = (*its).x4;
for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
if ((*itr).id == x2p) {
f = false;
break;
}
}
}
}
if (f == true) {
solid.push_back(pos);
}
}
//x2n
int x2n = (*itc).second.x2n;
if (x2n != ) {
if (cubes[x2n].x2p != id) {
ok = false;
break;
}
bool f = true;
Pos pos;
for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
if (f == false) break;
if ((*its).id == id) {
pos.id = x2n;
pos.x1 = (*its).x1;
pos.x2 = (*its).x2 - ;
pos.x3 = (*its).x3;
pos.x4 = (*its).x4;
for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
if ((*itr).id == x2n) {
f = false;
break;
}
}
}
}
if (f == true) {
solid.push_back(pos);
}
} //x3p
int x3p = (*itc).second.x3p;
if (x3p != ) {
if (cubes[x3p].x3n != id) {
ok = false;
break;
}
bool f = true;
Pos pos;
for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
if (f == false) break;
if ((*its).id == id) {
pos.id = x3p;
pos.x1 = (*its).x1;
pos.x2 = (*its).x2;
pos.x3 = (*its).x3 + ;
pos.x4 = (*its).x4;
for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
if ((*itr).id == x3p) {
f = false;
break;
}
}
}
}
if (f == true) {
solid.push_back(pos);
}
}
//x3n
int x3n = (*itc).second.x3n;;
if (x3n != ) {
if (cubes[x3n].x3p != id) {
ok = false;
break;
}
bool f = true;
Pos pos;
for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
if (f == false) break;
if ((*its).id == id) {
pos.id = x3n;
pos.x1 = (*its).x1;
pos.x2 = (*its).x2;
pos.x3 = (*its).x3 - ;
pos.x4 = (*its).x4;
for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
if ((*itr).id == x3n) {
f = false;
break;
}
}
}
}
if (f == true) {
solid.push_back(pos);
}
}
//x4p
int x4p = (*itc).second.x4p;
if (x4p != ) {
if (cubes[x4p].x4n != id) {
ok = false;
break;
}
bool f = true;
Pos pos;
for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
if (f == false) break;
if ((*its).id == id) {
pos.id = x4p;
pos.x1 = (*its).x1;
pos.x2 = (*its).x2;
pos.x3 = (*its).x3;
pos.x4 = (*its).x4 + ;
for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
if ((*itr).id == x4p) {
f = false;
break;
}
}
}
}
if (f == true) {
solid.push_back(pos);
}
}
//x4n
int x4n = (*itc).second.x4n;
if (x4n != ) {
if (cubes[x4n].x4p != id) {
ok = false;
break;
}
bool f = true;
Pos pos;
for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
if (f == false) break;
if ((*its).id == id) {
pos.id = x4n;
pos.x1 = (*its).x1;
pos.x2 = (*its).x2;
pos.x3 = (*its).x3;
pos.x4 = (*its).x4 - ;
for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
if ((*itr).id == x4n) {
f = false;
break;
}
}
}
}
if (f == true) {
solid.push_back(pos);
}
}
}
if (solid.size() != n) {
ok = false;
}
if (ok == false) {
cout << "Inconsistent" << endl;
continue;
}
int x1min = ;
int x1max = -;
int x2min = ;
int x2max = -;
int x3min = ;
int x3max = -;
int x4min = ;
int x4max = -;
for (vector<Pos>::iterator it = solid.begin(); it != solid.end(); ++it) {
if (x1min >(*it).x1) x1min = (*it).x1;
if (x1max < (*it).x1) x1max = (*it).x1;
if (x2min >(*it).x2) x2min = (*it).x2;
if (x2max < (*it).x2) x2max = (*it).x2;
if (x3min >(*it).x3) x3min = (*it).x3;
if (x3max < (*it).x3) x3max = (*it).x3;
if (x4min >(*it).x4) x4min = (*it).x4;
if (x4max < (*it).x4) x4max = (*it).x4;
}
int vol = (x1max - x1min + ) * (x2max - x2min + ) * (x3max - x3min + ) * (x4max - x4min + );
cout << vol << endl;
}
system("pause");
return ;
}