Восхождение 10

Алексея пригласили в Египет как специалиста по телекоммуникациям. На некоторой территории расположены N вертикальных вышек связи. Каждая вышка связи имеет координаты x, y и высоту h. Необходимо вершины всех этих вышек соединить оптоволоконной нитью в единую сеть. Стоимость отрезка нити равна квадрату длины этого отрезка, т.к. чем длиннее кусок нити, тем она должна быть крепче чтобы не порваться.

Алексей предложил в некоторых местах поставить дополнительные опоры, но власти Каира посчитали это дорогим «удовольствием», поэтому позволили установить не более одной опоры. Стоимость установки опоры равна кубу её высоты. Поэтому не всегда выгодно вообще устанавливать эту опору. Алексей предложил уже несколько вариантов по минимизации стоимости проекта. Ваша программа успешно проходит тест, если Ваш вариант решения не хуже чем у Алексея. Считать, что все отрезки оптоволоконной нити прямые (не провисают).

Входные данные

Входной файл INPUT.TXT содержит в первой строке натуральное число N (2 ≤ N ≤ 16). Далее в N строках идёт описание каждой вышки: целые координаты x, y и натуральное число высота h (-1000 ≤ x, y ≤ 1000; 1 ≤ h ≤ 1000).

Выходные данные

В выходной файл OUTPUT.TXT выведите в первой строке суммарную стоимость проекта с точностью до 3 знаков после запятой. Во второй строке выведите число K (0 или 1 (0 означает, что дополнительная опора не нужна, 1 - нужна)). Если K = 1, то в следующей строке с точностью до 3-х знаков после запятой выведите координаты установки опоры x_p, y_p и её высоту h_p. В следующих N строках выведите через пробел номера вышек в порядке возрастания, с которыми связана i-ая вышка. Дополнительная опора имеет номер «0».

Примеры

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]