Вам дано множество векторов на плоскости, начинающихся в точке (0, 0). Требуется найти любую пару векторов, таких что образованный ими неориентированный угол минимален.
Неориентированный угол — это неотрицательная величина, минимальный из двух углов от одного вектора до другого по или против часовой стрелки. Это значение всегда от 0 до π. Например, два противонаправленных вектора имеют угол между собой равный π.
В первой строке находится целое положительное число n (2 ≤ n ≤ 100 000) — количество векторов.
В i-й из следующих n строк записаны два целых числа xi и yi (|xi|, |yi| ≤ 10 000, x2 + y2 > 0) — координаты i-го вектора. Гарантируется, что среди векторов нет сонаправленных (но могут быть противонаправленные).
Выведите два целых числа a и b (a ≠ b) — пару индексов векторов, образующих минимальный неориентированный угол среди заданного множества векторов. Номера можно выводить в любом порядке. Если правильных ответо несколько, разрешается вывести любой.
4 -1 0 0 -1 1 0 1 1
3 4
6 -1 0 0 -1 1 0 1 1 -4 -5 -4 -6
6 5
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач