Convention Center
By Unknown 
Brazil
By Unknown Brazil
Now with the World Finals Programming Marathon in mind, the Chinese government started a project for the construction of a new convention center. This center will be the most modern in the world, with the entire infrastructure to host major events. The government has already decided (and if it was decided, it is decided) to build it in the shape of a circle. When viewed from above this new center, with the help of all its last generation lights, will give the impression of being a big rounded spaceship. With tricks of lights, is intended to create even an impression of movement to the majestic building.
But everyone knows that China has a big problem of physical space, and the only place available for building is on the outskirts of an ancient forest of ancient trees. To make the project even more attractive, it was decided that the center will be built within the forest, but without dropping a single tree. The luck of the designer is that the forest is sparse, and there is enough space between the trees in some places. Since you want to create the largest possible (in terms of built area) convention center, your task is to help find the best place to building. Your goal is to find the coordinates of the midpoint of construction, which shall be within the convex hull induced by trees.
The input is composed of several instances. Each instance starts with a line containing the number 0 ≤ n ≤ 1000 of trees in the forest, followed by n lines containing the ordered pairs xi yi, representing the coordinates of the trees of the forest. All coordinates given are integers. The input ends with n = 0.
For each solved instance, you should print an identifier ‘Instancia h’ where h is an integer, increasing and sequential number starting from 1. On the next line you should print an ideal central point, x y position, for the convention center. If there are more than an ideal point for building, print the one with the lowest value for x. Provided there is more than one option, print the one with the smallest value for y. Truncate the numbers printed in exactly three decimal places. If it is unable to build the center, write the word ‘impossivel’ in the line.
A blank line should separate the output of each instance.
| Sample Input | Sample Output |
|
4 |
Instancia 1 |