EMPTY - Empty Cuboids
We call a cuboid regular if:
- one of its vertices is a point with coordinates (0,0,0),
- edges beginning in this vertex lie on the positive semi-axes of the coordinate system,
- the edges are not longer than 10^{6}
There is given a set A of points of space, whose coordinates are integers from the interval [1..10^{6}]. We try to find a regular cuboid of maximal volume which does not contain any of the points from the set A. A point belongs to the cuboid if it belongs to the interior of the cuboid, i.e. it is a point of the cuboid, but not of its wall.
Task
Write a program which:
- reads from the standard input the coordinates of points from the set A,
- finds one of the regular cuboids of maximal volume which does not contain any points from the set A,
- writes the result to standard output.
Input
Input begins with a line containing integer t<=10, the number of test cases. t test cases follow.
In the first line of each test case one non-negative integer n is written ( n <= 5000). It is the number of elements in the set A. In the following n lines of the input there are triples of integers from the interval [1..10^{6}], which are the X, Y and Z coordinates of points from A, repectively. Numbers in each line are separated by single spaces.
Output
For each test case there should be three integers separated by single spaces. These are the X, Y and Z coordinates (respectively) of the vertex of the regular cuboid of maximal volume. If there is more than one such a cuboid, choose whichever. We require that all coordinates be positive.
Example
Sample input: 1 4 3 3 300000 2 200000 5 90000 3 2000 2 2 1000 Sample output: 1000000 200000 1000
hide comments
weathervane:
2017-11-11 10:44:54
The question should have said there is a blank line between every test case. That cost me several SIGSEGV failures. Last edit: 2017-11-11 10:49:22 |
Added by: | Piotr Ćowiec |
Date: | 2004-09-13 |
Time limit: | 7s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS PERL6 VB.NET |
Resource: | 6th Polish Olympiad in Informatics, stage 1 |