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

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

Ограничение времени: 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