아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

트리 긋기

면접 대비

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

요약
서로 다른 N개의 점이 주어질 때, 교차하지 않는 N-1개의 선분으로 트리를 만들어 출력한다.
난이도

보통10점 중 7점

유형
기하, 그리디
정답자
아직 제출이 없습니다

문제

22차원 평면 위에 NN개의 점이 주어진다. 선분 N−1N - 1개를 그어 트리를 만드시오. 단, 그은 선분 중 어떠한 두 선분도 서로 교차하면 안 된다.

어떤 선분의 끝점이 다른 선분 위에 있는 것은 교차하는 경우이다. 두 선분이 끝점에서 만나는 것은 교차하는 경우가 아니다.

입력

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

두 번째 줄부터 NN개의 줄에 걸쳐 점의 좌표가 주어진다. 그중 ii번째 줄에는 ii번 점의 좌표 정수 x_ix\_i, y_iy\_i가 공백으로 구분되어 주어진다. (−109≤x_i,y_i≤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