트리 긋기
면접 대비시간 제한1초메모리 제한1024 MB
평면 위의 N개 점을 서로 교차하지 않는 N-1개의 선분으로 이어 트리를 만드는 방법을 구합니다.
문제
2차원 평면 위에 개의 점이 주어진다. 선분 개를 그어 트리를 만드시오. 이때 그은 선분 중 어떤 두 선분도 서로 교차해서는 안 된다.
한 선분의 끝점이 다른 선분 위에 있으면 두 선분은 교차하는 것이다. 두 선분이 끝점에서만 만나는 경우는 교차하지 않는 것이다.
입력
첫 번째 줄에 점의 개수 이 주어진다. ()
두 번째 줄부터 개의 줄에 걸쳐 점의 좌표가 주어진다. 번째 줄에는 번 점의 좌표인 정수 와 가 공백으로 구분되어 주어진다. ()
주어지는 모든 점의 좌표는 서로 다르다.
출력
트리를 구성하는 선분을 개의 줄에 출력한다. 각 줄에는 선분을 이루는 두 점의 번호를 공백으로 구분하여 출력한다.
트리를 긋는 방법이 여럿인 경우에는 그중 아무거나 하나를 출력한다.