VI Olimpiada Informatyczna 1998/1999
|
Task: PUS
|
Author:
|
I stage contest |
We call a cuboid regular if:
There is given a set A of points of space, which coordinates are integers from the interval [1..106]. 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 inside of the cuboid, i.e. it is a point of the cuboid, but not of its wall.
Write a program which:
In the first line of the input file PUS.IN one non-negative integer n, n <= 5000, is written. It is the number of elements in the set A. In the following n lines of the file PUS.IN there are triples of integers from the interval [1..106], which are coordinates (respectively x, y and z) of points from A. Numbers in each line are separated by single spaces.
In the only line of the output file PUS.OUT there should be three integers separated by single spaces. These are coordinates (respectively x, y and z) of the vertex of the regular cuboid of maximal volume. We require that coordinates are positive.
For the input file PUS.IN:
4 3 3 300000 2 200000 5 90000 3 2000 2 2 1000
the correct answer is the file PUS.OUT:
1000000 200000 1000
Your program should look for the file PUS.IN in the current directory and produce the output file PUS.OUT in current directory too. The file containing source code of your program should have a name PUS.???, whereas you should put three-letter abbreviation of used programming language name instead of ???. The same program in executable form should be written in the file PUS.EXE