|
I |
All
Souls Night Input: Standard Input Output: Standard Output |
|
“Standing
on the bridge that crosses the river that goes out to the sea
The wind is full of a thousand voices, they pass by the bridge and me
I can see the lights in the distance trembling in the dark cloak of night
Candles and lanterns are dancing, dancing a waltz on all souls night.”
In the
traditional all souls night celebration, souls of the departed are commemorated
by sending candle-lit lanterns on out waterways leading to the oceans, sometimes in little boats. A single lantern
represents an individual soul drifting away to the next world. Let's assume the
position of a lantern just at the moment of entering the next world is given by
the coordinates of a single point in 3-d space. A pair of souls can communicate
with each other by straight-lined light rays joining themselves.
As soon as the souls enter
afterlife, they are covered by a mysterious veil which separates themselves
from the distant living world. The veil should be placed in such a way that the
communication beams between any two souls are entirely contained within the
veil in order to prevent the living world people overhearing them. Now, as the
weavers of heaven are tired of going on knitting veils for an eternity, they
ask for your help. You are asked to calculate the minimum surface area of the
veil required to cover a group of souls fulfilling the restrictions given
above. Help Heaven!
Input
The
input file will contain multiple test cases. Each case begins with an integer N
(3 < N < 26), the number of souls in a group. Each of the following N lines contains 3 integers giving the x,
y and z coordinates of a single soul (-100 <= x, y, z <=
100). They will be positioned in
such a way that there won't be more than 3 souls in any polygonal face of the
veil. The end of input will be marked by a case with N = 0. This case
should not be processed.
Output
For each
test case, print a line in the format, “Case X: Y”, where
X is the case number & Y is the minimum required surface area of
the veil. Print 2 digits after the decimal point for Y.
Sample
Input
Output for Sample Input
|
4 0 0 0 4 0 0 0 4 0 0 0 4 0 |
Case 1: 37.86 |
Problemsetter: Mohammad Mahmudur Rahman
Special Thanks: Jane Alam Jan