POJ 1188 - Gleaming the Cubes

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

概要

\(N\) 個の立方体が与えられるので、これらの共通部分の体積を答える。 立方体の各辺は、x, y, z 軸のいずれかに並行である。

制約

• \(2 \le N \le 1000\)

解法

共通部分は直方体になる。やるだけ。

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (cin >> N && N != 0) {
 9     int x1, x2, y1, y2, z1, z2;
10     int d;
11     cin >> x1 >> y1 >> z1 >> d;
12     x2 = x1+d;
13     y2 = y1+d;
14     z2 = z1+d;
15     for (int i = 1; i < N; i++) {
16       int x, y, z;
17       cin >> x >> y >> z >> d;
18       x1 = max(x1, x);
19       x2 = min(x2, x+d);
20       y1 = max(y1, y);
21       y2 = min(y2, y+d);
22       z1 = max(z1, z);
23       z2 = min(z2, z+d);
24     }
25     cout << max(0, (x2-x1)*(y2-y1)*(z2-z1)) << endl;
26   }
27   return 0;
28 }