400907: GYM100283 A Rasheda And The Zeriba

Yesterday a strong storm hit the city, destroying many of the animals’ stables. Unfortunately Bakkar's little cute goat (Rasheda) was not lucky, and her zeriba (stable) was also destroyed by the storm.

Bakkar is now searching for a better place for Rasheda, so he decided to buy a new piece of land to build Rasheda’s zeriba on it. The land owner only sells circular pieces of land. Bakkar has only a little amount of money to buy land and build the zeriba on it. Fortunately Bakkar managed to recover most of the wooden walls of the old zeriba, so he will use them to build the new one without buying new walls. To minimize the amount of money spent, Bakkar has to buy the smallest piece of land that can enclose the zeriba he is building.

To build the zeriba Bakkar uses the following strategy; using the N walls recovered Bakkar would construct a non-degenerate convex polygon to build the zeriba. For construction purposes the walls of the new zeriba must be in the same order as they were in the old one.

Now given the N lengths of the walls recovered, Bakkar will construct the zeriba so that it is a non-degenerate convex polygon with N sides, using the same order of the given walls. Bakkar then needs to know the radius of the smallest circle that can surround the entire polygon.

As you are a geometry lover, Bakkar called you to ask for you help. He will tell you the lengths of the walls then you would tell him the radius of the minimum circle that can enclose the zeriba if it is possible to construct a non-degenerate convex polygon using the sides. If it is not possible you would tell him that it's impossible.

P.S.: A convex polygon is a polygon that has no angles pointing inwards. More precisely, no internal angle can be more than . A non-degenerate polygon is a polygon with a non-zero area.

The above figure illustrates a possible configuration of the first sample input in which there are 5 walls with lengths 5,5,2,3 and 1 respectively.

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  100). Followed by T test cases, each test case start with a single integer N, the number of walls recovered (3  ≤  N  ≤  1000). Following this, there are N space-separated positive integers, representing the length of each wall in anti-clockwise order. The length of each wall will not be more than 1000.

For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by a single space, then a single real number representing the radius of the smallest circle the zeriba can fit in. Each output must be rounded to the nearest 0.0001 and must be printed with exactly four digits after the decimal point. If you can't form a convex polygon from the given walls just print "can't form a convex polygon" (without the quotes).

2
5
5 5 2 3 1
3
5 1 1

Case 1: 2.9039
Case 2: can't form a convex polygon