Вступление
Мэр Тмутаракани Сергей Живодёров любит две вещи — животных и охоту. Как-то раз на заседании Городской Думы он посетовал на то, что избирателям очень не хватает территории, где в комфортных условиях могли бы охотиться первые лица города. Депутаты прислушались к мнению избирателей и издали постановление об учреждении Национального Парка Тмутаракани в местном лесу. Обязанность определения границ будущего Парка была возложена на Правительственный Комитет по Природопользованию, который в свою очередь делегировал эти полномочия Городскому Лесничеству в лице егеря Кузьмича.
Задача
Кузьмич вооружился мотком колючей проволоки и отправился в лес. Прибыв на местность, он обнаружил, что в лесу N деревьев, пронумерованных от 1 до N, и определил их декартовы координаты (Xi, Yi).
Кузьмич знал, что проще всего последовательно обвязать колючей проволокой три любых дерева c различными номерами. Тогда получившийся треугольник обозначит границы Национального Парка. А ещё он знал, что колючая проволока тоже стоит денег, и решил выбрать эти три дерева таким образом, чтобы периметр Парка был наименьшим.
Исходные данные
Первая строка содержит целое число N (3 ≤ N ≤ 50000). Каждая из следующих N строк содержит целые числа Xi и Yi (-106 ≤ Xi, Yi ≤ 106) для соответствующего дерева.
Результат
В первую строку вывести минимальный периметр Национального Парка не менее чем с четырьмя знаками после десятичной точки. Во вторую строку вывести через пробел и в любом порядке номера тех трёх деревьев, вокруг которых Кузьмич должен обвязать колючую проволоку. Если задача имеет несколько решений, то вывести любое из них.
Пример
исходные данные | результат |
---|
5
0 0
1 1
3 0
0 3
3 3
| 6.6503
1 2 3
|
Замечания
Странные вещи творятся в тмутараканском лесу — координаты некоторых деревьев могут совпадать, а треугольник нулевой площади всё равно считается треугольником.
Автор задачи: Никита Рыбак, Илья Гребнов, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: Third Challenge