The Fence Builder

A fence builder has been given a strange task. Provided with N (between 3 and 100) pieces of straight fencing, each having an arbitrary length, the builder is to enclose as large a region as possible. The customer wants to know the area of the region that can be enclosed by the fence before it is built. There is only one constraint on the construction: each piece of fencing is connected only at its endpoints to exactly two other different pieces of fencing. That is, after completion, the fence will look like a (possibly irregular) polygon with N sides. The customer has guaranteed the builder that the fencing provided will allow for a region with a non-zero area to be enclosed.

Input Specification

There will be multiple cases in the input. For each case, the input begins with the number of pieces of fencing (an integer, N). There then follow N positive, non-zero real numbers giving the lengths of the fence pieces. A single integer zero follows the last case in the input.

Output Specification

For each case, display the case number (starting with 1) and the maximum area that can be enclosed by the provided fencing materials. Show three fractional digits in each answer. Use the format shown below in displaying the results.

Sample Input

1. 3 2.0 2.0 2.0
2. 4 1.0 1.0 1.0 1.0
3. 4 5.0 5.0 3.0 11.0
4. 0

download as text file

Output for Sample Input

1. Case 1: maximum area = 1.732
2. Case 2: maximum area = 1.000
3. Case 3: maximum area = 21.000

download as text file