← 返回题目列表

Codeforces · 598/C

C. 最近的向量

中文机器翻译题面 查看原题

给定平面上的一组向量,每个向量都从原点开始。您的任务是找到一对向量,它们之间的无方向角最小。

非定向角是非负值,顺时针方向角和逆时针方向角之间的最小值。无方向角总是在 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