시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 512 MB 29 2 2 8.696%

문제

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

3 2 4 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)이 있다.

예제 입력 2

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

예제 출력 2

3 4 5 4

노트

두 벡터 v = (xv, yv), u = (xu, vu)의 합은 s = v + u = (xv + xu, yv + yu) 이다.

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

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013