Throw the Stones
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 15 Accepted Submission(s): 2
Problem Description
Remember our childhood? A few naked children throw stones standing on the same position, the one throws farther win the game. Aha, of course, there are some naughty boys who care more about whether they can urinate father.
You believe it or not, anyway, I believed. Nowadays, some of the children are smarter than we were, while others may be more naughty.
A week ago, I saw several children throw stones. In fact, they are more clever than we were, since the game they played, apparently, is more complex than we did. Maybe you have different points of view, however, you’d better learn about the rules of the game before expressing your views. A group of children take turns to throw stones standing on the same position. After some child throw a stone, the children will draw a convex polyhedron with smallest volume together to enclose all the stones thrown by them. You may assume that the stone is so small as to be abstracted as a point in three-dimensional space. Naively, the children regard the space enclosed by the convex polyhedron as territory under their control. After a child throw his stone, the score he obtains equals the incremental of the volume of their territory. Unfortunately, the first three child’s score will always be zero. At last, the child with the highest score will win the game, and known as the "King".
I think you have accepted my opinion already, for the rules of their throwing stones game are really complicated. But, you also don’t need to be frustrated for it. Now, in order to show you are smarter, maybe you can write a program to help the children point out their "King".
You believe it or not, anyway, I believed. Nowadays, some of the children are smarter than we were, while others may be more naughty.
A week ago, I saw several children throw stones. In fact, they are more clever than we were, since the game they played, apparently, is more complex than we did. Maybe you have different points of view, however, you’d better learn about the rules of the game before expressing your views. A group of children take turns to throw stones standing on the same position. After some child throw a stone, the children will draw a convex polyhedron with smallest volume together to enclose all the stones thrown by them. You may assume that the stone is so small as to be abstracted as a point in three-dimensional space. Naively, the children regard the space enclosed by the convex polyhedron as territory under their control. After a child throw his stone, the score he obtains equals the incremental of the volume of their territory. Unfortunately, the first three child’s score will always be zero. At last, the child with the highest score will win the game, and known as the "King".
I think you have accepted my opinion already, for the rules of their throwing stones game are really complicated. But, you also don’t need to be frustrated for it. Now, in order to show you are smarter, maybe you can write a program to help the children point out their "King".
Input
Input consists of a number of cases. The data of each case appears on a number of input lines, the first of which contains an integer N. The following N lines contain three number (xi, yi, zi) indicating coordinates of the stone thrown by the i-th child.
Note: 1 <= N <= 10^4, 1 <= i <= N, -10^4 <= xi , yi , zi <= 10^4.
Note: 1 <= N <= 10^4, 1 <= i <= N, -10^4 <= xi , yi , zi <= 10^4.
Output
For each test case, you should output two lines. The first line is "Case #K:", K means the number of the test case. The second line is "i v", i means index of the "King" and v means the score of the "King". If there are more than one "King", output the one throws stone earlier than others.
Please round the result to 2 digits after decimal point if necessary.
Please round the result to 2 digits after decimal point if necessary.
Sample Input
4 1 0 0 1 1 0 0 1 0 0 0 1 5 1 0 0 1 1 0 0 1 0 0 0 0 0 0 1
Sample Output
Case #1： 4 0.17 Case #2： 5 0.33