← 返回题目列表

Codeforces · 120/J

J. 最小总和

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

给定一个平面上的一组 n 个向量。对于每个向量,您可以将其任何坐标乘以 -1。因此,每个向量 vi = (xi, yi) 可以变换为以下四个向量之一:

- vi1 = (xi, yi),
- vi2 = ( - xi, yi),
- vi3 = (xi,  - yi),
- vi4 = ( - xi,  - yi)。

您应该从集合中找到两个向量,并确定其中哪个坐标应乘以 -1,以便所得向量之和的绝对值尽可能小。更正式地说,您应该选择两个向量 vi, vj (1 ≤ i, j ≤ n, i ≠ j) 和两个数字 k1, k2 (1 ≤ k1, k2 ≤ 4),使得表达式 |vik1 + vjk2| 的值是最小的。

输入

第一行包含一个整数 n (2 ≤ n ≤ 105)。然后 n 行包含向量作为整数对“xi yi”(- 10000 ≤ xi, yi ≤ 10000),每行一对。

输出

在第一行打印四个空格分隔的数字“i k1 j k2”——问题的答案。如果有多个变体的总和绝对值最小,则可以打印其中任何一个。

示例

输入 #1

5
-7 -3
9 0
-8 6
7 -8
4 -5

输出 #1

3 2 4 2

输入 #2

5
3 2
-4 7
-6 0
-8 4
5 1

输出 #2

3 4 5 4

注意

两个向量 v = (xv, yv) 和 u = (xu, yu) 之和为向量 s = v + u = (xv + xu, yv + yu)。

向量 v = (x, y) 的绝对值为数字 $$|v| = \sqrt{x^2 + y^2}$$。

在第二个示例中,有几个有效答案,例如:

(3 1 4 2), (3 1 4 4), (3 4 4 1), (3 4 4 3), (4 1 3 2), (4 1 3 4), (4 2 3 1).