Problem D. Deliver barbed wire

Author:I. Ludov   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

Dedicated to the 25th anniversary of the Elite game.

The planet Lave has a form of a perfect sphere. There are N cities on the surface of the planet. Each city may belong to one of several countries.

The history of Lave knows many wars and annexations, so government of each country tries to keep it's territory simple in shape and it's borders short.

If cities A and B are located in the same country, the shortest path from A to B lies fully within that country. Furthermore, if three cities A, B and C are all located in the same country, the shortest path from C to every point of the shortest path form A to B also lies fully within that country.

The border of each country is continuous, connected (no enclaves), and as short as possible while keeping all the above mentioned properties. All countries have non-zero area.

Some parts of the planet surface may remain neutral. In particular, Lave international conventions state that Northern and Southern poles never belong to any country.

Space merchant and freelancer Dave B. is planning a business trip to Lave. He wants to sell some barbed wire to the country with the longest perimeter. Unfortunately for him, the political situation on Lave changes so rapidly, that he is not sure about which city will belong to which country at the moment he arrives.

So, Dave hired you to calculate the longest length of country border over all possible city allegiances.

Input file format

Input file contains integer N — number of cities, followed by N triplets of real numbers xi yi zi — city coordinates. The center of the planet is located at point (0, 0, 0). Both poles lie on Oz axis.

Output file format

Output file must contain a single real number with at least 5 correct digits after the decimal point — the longest possible country perimeter. If the cities are located so that no countries can exist, output "0".

Constraints

3 ≤ N ≤ 1000, 1 ≤ r ≤ 1000, where r is the planet radius.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
1 0 0
0 1 0
0.577350269 0.577350269 0.577350269
3.48143

0.060s 0.009s 13