Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Выпуклая оболочка

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

24/06/2010 | Лето 2010 дорешивание ( 9D) |

12/07/2010 | Лето 2010 - 9 (D) |

*Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

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 contains integer `N` – number of cities, followed by `N` triplets of real numbers `x_i\ y_i\ z_i` – city coordinates. The center of the planet is
located at point `(0,\ 0,\ 0)`. Both poles lie on `"Oz"` axis.

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`".

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

Sample Input

3 1 0 0 0 1 0 0.577350269 0.577350269 0.577350269

Sample Output

3.48143