16885번 - 벡터의 합 스페셜 저지

2차원 벡터 N개가 있다. 각각의 벡터는 좌표에 -1을 곱하는 연산을 적용할 수 있다. 예를 들어, v = (x, y) 라면, 아래 4가지 중 하나로 변형할 수 있다.

• 1: (x, y)
• 2: (-x, y)
• 3: (x, -y)
• 4: (-x, -y)

N개의 벡터 중 두 개 v_i, v_j를 골라 |v_i + v_j|의 최솟값을 구하는 프로그램을 작성하시오. 벡터에는 위의 연산을 적용해 4가지 중 하나로 변형할 수 있다.

첫째 줄에 벡터의 개수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 i번째 벡터 v_i의 좌표 x_i, y_i(-10,000 ≤ x, y ≤ 10,000)가 한 줄에 하나씩 주어진다.

첫째 줄에 네 개의 정수 i, k₁, j, k₂를 공백으로 구분해 출력한다. i와 j는 고른 벡터의 인덱스이고, k₁, k₂는 적용한 연산의 번호이다. 최소가 되는 정답이 여러가지인 경우에는 아무거나 출력한다.

두 벡터 v = (x_v, y_v), u = (x_u, y_u)의 합은 s = v + u = (x_v + x_u, y_v + y_u) 이다.

벡터 v = (x, y)의 |v|는 √(x² + y²) 이다.