Minimum Sum

题意翻译

- **本题需文件操作**，从 `input.txt` 读入，输出到 `output.txt`。 - 给出 $n$ 个向量。 - 对于任意一个向量 $v_i=(x_i,y_i)$，你可以使之变成一下之一： - $v_i^1 = (x_i, y_i)$ - $v_i^2=(-x_i, y_i)$ - $v_i^3=(x_i,-y_i)$ - $v_i^4=(-x_i,-y_i)$ - 你需要找到一组 $1\le i, j \le n, i\neq j, 1\le k_1,k_2\le 4$ 使得 $|v_i^{k_1}+v_j^{k_2}|$ 最小。其中 $|a|$ 为向量 $a$ 的模长。

题目描述

You are given a set of $ n $ vectors on a plane. For each vector you are allowed to multiply any of its coordinates by -1. Thus, each vector $ v_{i}=(x_{i},y_{i}) $ can be transformed into one of the following four vectors: - $ v_{i}^{1}=(x_{i},y_{i}) $ , - $ v_{i}^{2}=(-x_{i},y_{i}) $ , - $ v_{i}^{3}=(x_{i},-y_{i}) $ , - $ v_{i}^{4}=(-x_{i},-y_{i}) $ . You should find two vectors from the set and determine which of their coordinates should be multiplied by -1 so that the absolute value of the sum of the resulting vectors was minimally possible. More formally, you should choose two vectors $ v_{i} $ , $ v_{j} $ ( $ 1<=i,j<=n,i≠j $ ) and two numbers $ k_{1} $ , $ k_{2} $ ( $ 1<=k_{1},k_{2}<=4 $ ), so that the value of the expression $ |v_{i}^{k_{1}}+v_{j}^{k_{2}}| $ were minimum.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2<=n<=10^{5} $ ). Then $ n $ lines contain vectors as pairs of integers " $ x_{i} $ $ y_{i} $ " ( $ -10000<=x_{i},y_{i}<=10000 $ ), one pair per line.

输出格式

Print on the first line four space-separated numbers " $ i $ $ k_{1} $ $ j $ $ k_{2} $ " — the answer to the problem. If there are several variants the absolute value of whose sums is minimum, you can print any of them.

输入输出样例

输入样例 #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

说明

A sum of two vectors $ v=(x_{v},y_{v}) $ and $ u=(x_{u},y_{u}) $ is vector $ s=v+u=(x_{v}+x_{u},y_{v}+y_{u}) $ . An absolute value of vector $ v=(x,y) $ is number . In the second sample there are several valid answers, such as: (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).