首页 > 专题系列 > Java解POJ > POJ 1188 Gleaming the Cubes [解题报告] Java
2013
11-09

POJ 1188 Gleaming the Cubes [解题报告] Java

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