给定平面上的一组向量,每个向量都从原点开始。您的任务是找到一对向量,它们之间的无方向角最小。
非定向角是非负值,顺时针方向角和逆时针方向角之间的最小值。无方向角总是在 0 和 π 之间。例如,相反方向的向量的角度等于 π。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 100 000) — 向量的数量。
以下 n 行中的第 i 行包含两个整数 xi 和 yi (|x|, |y| ≤ 10 000, x2 + y2 > 0) – 第 i 个向量的坐标。向量按照输入中出现的顺序从 1 到 n 编号。确保输入中没有两个向量具有相同的方向(但它们仍然可以具有相反的方向)。
输出
打印两个整数 a 和 b (a ≠ b) - 一对具有最小无方向角的向量索引。您可以按任何顺序打印数字。如果有很多可能的答案,请打印任何一个。
示例
输入 #1
4 -1 0 0 -1 1 0 1 1
输出 #1
3 4
输入 #2
6 -1 0 0 -1 1 0 1 1 -4 -5 -4 -6
输出 #2
6 5