Загрузка [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
 

print1009. Самый острый угол

printСамый острый угол

Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В данном множестве из N точек на плоскости с координатами (xi,  требуется найти такие три точки A, B и C, что угол "ABC" будет наименьшим.
Никакие три точки в исходном множестве не лежат на одной прямой.
Ввод
Во входном файле содержится число N, за которым следует N пар целых чисел x_i\ y_i.
Вывод
В выходном файле должно содержаться три целых числа A\ B\ C — номера вершин минимального угла. Точки нумеруются с 1. Если решений несколько, выведите любое из них.
Ограничения
3\ ≤\ N\ ≤\ 10^3, 0\ ≤\ x_i,\ y_i\ ≤\ 10^6

Пример ввода

3
5 5  5 4  10 4

Пример вывода

1 3 2
Источник: А. Кленин, ДВГУ, Весенний турнир, 2008
loading