만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

트리 긋기

면접 대비

시간 제한1초메모리 제한1024 MB

요약
평면 위의 N개 점을 서로 교차하지 않는 N-1개의 선분으로 이어 트리를 만드는 방법을 구합니다.
난이도

보통10점 중 4점

유형
정렬, 구현
정답자
아직 제출이 없습니다

문제

2차원 평면 위에 NN개의 점이 주어진다. 선분 N−1N - 1개를 그어 트리를 만드시오. 이때 그은 선분 중 어떤 두 선분도 서로 교차해서는 안 된다.

한 선분의 끝점이 다른 선분 위에 있으면 두 선분은 교차하는 것이다. 두 선분이 끝점에서만 만나는 경우는 교차하지 않는 것이다.

입력

첫 번째 줄에 점의 개수 NN이 주어진다. (2≤N≤1 0002 \le N \le 1\,000)

두 번째 줄부터 NN개의 줄에 걸쳐 점의 좌표가 주어진다. ii번째 줄에는 ii번 점의 좌표인 정수 xix_i와 yiy_i가 공백으로 구분되어 주어진다. (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9)

주어지는 모든 점의 좌표는 서로 다르다.

출력

트리를 구성하는 선분을 N−1N - 1개의 줄에 출력한다. 각 줄에는 선분을 이루는 두 점의 번호를 공백으로 구분하여 출력한다.

트리를 긋는 방법이 여럿인 경우에는 그중 아무거나 하나를 출력한다.

예제2

  1. 예제 1

    입력
    4
    0 0
    -1 0
    1 1
    1 -1
    
    예상 출력
    2 1
    3 1
    4 1
    
  2. 예제 2

    입력
    7
    1 1
    3 3
    4 0
    3 1
    4 -2
    6 -2
    4 -3
    
    예상 출력
    1 4
    2 4
    4 3
    3 5
    5 6
    5 7