ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Timus Top Coders: Third Challenge

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Национальный парк

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

Мэр Тмутаракани Сергей Живодёров любит две вещи — животных и охоту. Как-то раз на заседании Городской Думы он посетовал на то, что избирателям очень не хватает территории, где в комфортных условиях могли бы охотиться первые лица города. Депутаты прислушались к мнению избирателей и издали постановление об учреждении Национального Парка Тмутаракани в местном лесу. Обязанность определения границ будущего Парка была возложена на Правительственный Комитет по Природопользованию, который в свою очередь делегировал эти полномочия Городскому Лесничеству в лице егеря Кузьмича.

Задача

Кузьмич вооружился мотком колючей проволоки и отправился в лес. Прибыв на местность, он обнаружил, что в лесу N деревьев, пронумерованных от 1 до N, и определил их декартовы координаты (Xi, Yi).
Кузьмич знал, что проще всего последовательно обвязать колючей проволокой три любых дерева c различными номерами. Тогда получившийся треугольник обозначит границы Национального Парка. А ещё он знал, что колючая проволока тоже стоит денег, и решил выбрать эти три дерева таким образом, чтобы периметр Парка был наименьшим.

Исходные данные

Первая строка содержит целое число N (3 ≤ N ≤ 50000). Каждая из следующих N строк содержит целые числа Xi и Yi (-106Xi, Yi ≤ 106) для соответствующего дерева.

Результат

В первую строку вывести минимальный периметр Национального Парка не менее чем с четырьмя знаками после десятичной точки. Во вторую строку вывести через пробел и в любом порядке номера тех трёх деревьев, вокруг которых Кузьмич должен обвязать колючую проволоку. Если задача имеет несколько решений, то вывести любое из них.

Пример

исходные данныерезультат
5
0 0
1 1
3 0
0 3
3 3
6.6503
1 2 3

Замечания

Странные вещи творятся в тмутараканском лесу — координаты некоторых деревьев могут совпадать, а треугольник нулевой площади всё равно считается треугольником.
Автор задачи: Никита Рыбак, Илья Гребнов, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: Third Challenge
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1514. Национальный парк