Submit | All submissions | Best solutions | Back to list |
ACPC10F - World of cubes |
You’ve been assigned the task of programming a new video game called the World of Cubes. The game is played inside a box-shaped object (mathematically speaking: a rectangular cuboid) which we’ll call the hall. Within the hall, the player is assigned N positions, called focal points.
The player must build N cubes, all parallel to the axes, and each is centered around one of the focal points. The mission is for the N cubes to completely fill the hall. It is acceptable for the cubes to overlap and even to extend beyond the hall. The only restriction is that all the cubes must be of equal side-length. And we would like you to compute the minimum such length.
Input
Your program will be tested on one or more test cases. Each test case is specified using N +1 lines.
The first line specifies four integers: (1 ≤ N ≤ 50) is the number of cubes and (1 ≤ X, Y, Z ≤ 109) are the dimensions of the hall. One corner of the hall is at the origin (0, 0, 0), with the opposing corner at (X, Y, Z).
N lines follow, each specifying the coordinate of a focal point using three integers: (0 ≤ x ≤ X), (0 ≤ y ≤ Y), and (0 ≤ z ≤ Z).
The last test case is followed by a line containing four zeros.
Output
For each test case, print the following line:
k. D
Where k is the test case number (starting at one,) and D is an integer which is the smallest length of the cube edges so that the N cubes would completely fill the hall.
Example
Input:
2 4 4 8
2 2 2
2 2 6
2 4 4 8
2 2 2
2 2 5
0 0 0 0
Output:
1. 4
2. 6
Added by: | Omar ElAzazy |
Date: | 2010-11-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | ACPC 2010 |