2013
11-09

# 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 consists of several sets of cubes for which the volume of their intersections must be computed. The first line of each set 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.A number =0 indicate the end of input.

Your program should process sets all 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.

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

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
static int mins=Integer.MIN_VALUE;
static int maxs=Integer.MAX_VALUE;

static int min(int a,int b)
{
return a<=b?a:b;
}

static int max(int a,int b)
{
return a>=b?a:b;
}

public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,i;
while(sc.hasNext())
{
n=sc.nextInt();
if(n==0)
break;
int startx=mins;
int starty=mins;
int startz=mins;
int stopx=maxs;
int stopy=maxs;
int stopz=maxs;
int x,y,z,len,h=0;
for(i=0;i< n;i++)
{
x=sc.nextInt();
y=sc.nextInt();
z=sc.nextInt();
len=sc.nextInt();
if(h==1)
continue;
startx=max(startx,x);
starty=max(starty,y);
startz=max(startz,z);
x=x+len;
y=y+len;
z=z+len;
stopx=min(stopx,x);
stopy=min(stopy,y);
stopz=min(stopz,z);
if(startx>=stopx || starty>=stopy || startz>=stopz)
h=1;
}
if(h==0)
{
System.out.println((stopx-startx)*(stopy-starty)*(stopz-startz));
}
else
System.out.println("0");
}
}
}

1. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）

2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。