2013
12-10

Gleaming the Cubes

As chief engineer of the Starship Interprize, the task of repairing the hyperstellar, cubic, transwarped-out software has fallen on your shoulders. Simply put, you must compute the volume of the intersection of anywhere from 2 to 1000 cubes.

The input data file consists of several sets of cubes for which the volume of their intersections must be computed. The first line of the data file contains a number (from 2 to 1000) which indicates the number of cubes which follow, one cube per line. Each line which describes a cube contains four integers. The first three integers are the x, y, and z coordinates of the corner of a cube, and the fourth integer is the positive distance which the cube extends in each of the three directions (parallel to the x, y, and z axes) from that corner.

Following the data for the first set of cubes will be a number which indicates how many cubes are in a second set, followed by the cube descriptions for the second set, again one per line. Following this will be a third set, and so on. Your program should continue to process sets of cubes, outputting the volume of their intersections to the output file, one set per line, until a zero is read for the number of cubes.Note that the data file will always contain at least one set of cubes, and every set will contain at least 2 and at most 1000 cubes. For any given set of cubes, the volume of their intersections will not exceed 1,000,000 units.

2
0 0 0 10
9 1 1 5
3
0 0 0 10
9 1 1 5
8 2 2 3
0

25
9

#include<iostream>
#include<vector>
using namespace std;
bool intersect( pair<int,int> a, pair<int,int> b, pair<int,int> &ret ){
ret.first = max(a.first, b.first);
ret.second = min(a.second, b.second);
if( ret.second <= ret.first ) return false;
else return true;
}
int main(){
while(true){
vector< pair<int, int> > xv, yv, zv;
int n;
cin >> n;
if( n == 0 ) break;
int intersected_x, intersected_y, intersected_z;
for(int i = 0; i < n; ++i){
int x, y, z, d;
cin >> x >> y >> z >> d;
xv.push_back( make_pair( x, x+d ) );
yv.push_back( make_pair( y, y+d ) );
zv.push_back( make_pair( z, z+d ) );
}
intersected_x = xv[0].second - xv[0].first;
intersected_y = yv[0].second - yv[0].first;
intersected_z = zv[0].second - zv[0].first;

if( n > 1 ){
pair<int,int> xintersect, yintersect, zintersect;

if( !intersect( xv[0], xv[1], xintersect ) )
intersected_x = 0;
else
intersected_x = xintersect.second - xintersect.first;
for(unsigned int i = 2; i < n; ++i){
if( !intersect( xintersect, xv[i], xintersect ) ){
intersected_x = 0;
break;
}
intersected_x = xintersect.second - xintersect.first;
}

if( !intersect( yv[0], yv[1], yintersect ) )
intersected_y = 0;
else
intersected_y = yintersect.second - yintersect.first;
for(unsigned int i = 2; i < n; ++i){
if( !intersect( yintersect, yv[i], yintersect ) ){
intersected_y = 0;
break;
}
intersected_y = yintersect.second - yintersect.first;
}

if( !intersect( zv[0], zv[1], zintersect ) )
intersected_z = 0;
else
intersected_z = zintersect.second - zintersect.first;
for(unsigned int i = 2; i < n; ++i){
if( !intersect( zintersect, zv[i], zintersect ) ){
intersected_z = 0;
break;
}
intersected_z = zintersect.second - zintersect.first;
}
}

//cout << intersected_x << " " << intersected_y << " " << intersected_z << endl;

cout << intersected_x * intersected_y * intersected_z << endl;
}
return 0;
}