29757번 - 트리 긋기 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 456 | 301 | 269 | 65.291% |
문제
$2$차원 평면 위에 $N$개의 점이 주어진다. 선분 $N - 1$개를 그어 트리를 만드시오. 단, 그은 선분 중 어떠한 두 선분도 서로 교차하면 안 된다.
어떤 선분의 끝점이 다른 선분 위에 있는 것은 교차하는 경우이다. 두 선분이 끝점에서 만나는 것은 교차하는 경우가 아니다.
입력
첫 번째 줄에 점의 개수 $N$이 주어진다. $(2 \le N \le 1\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 점의 좌표가 주어진다. 그중 $i$번째 줄에는 $i$번 점의 좌표 정수 $x_i$, $y_i$가 공백으로 구분되어 주어진다. $(-10^9 \le x_i, y_i \le 10^9)$
주어지는 모든 점의 좌표는 서로 다르다.
출력
$N - 1$개의 줄에 걸쳐 트리를 구성하는 선분을 출력한다. 각 줄에는 선분을 이루는 두 점의 번호를 공백으로 구분하여 출력한다.
트리를 긋는 방법이 여럿인 경우는 그중 아무거나 하나를 출력한다.
예제 입력 1
4 0 0 -1 0 1 1 1 -1
예제 출력 1
2 1 3 1 4 1
예제 입력 2
7 1 1 3 3 4 0 3 1 4 -2 6 -2 4 -3
예제 출력 2
1 4 2 4 4 3 3 5 5 6 5 7
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호