22874번 - Distance on Triangulation 2 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 49 | 17 | 14 | 36.842% |
문제
뜨룹랜드는 정점이 $2N$개인 볼록다각형 모양의 왕국이다.
볼록다각형의 각 정점에는 집이 하나씩 있다. 집들은 시계 방향으로 1부터 $2N$까지 번호가 매겨져 있다.
다각형의 둘레를 따라 $2N$개의 양방향 도로가 지어져 있다. 즉 모든 $i(1 \leq i < 2N)$에 대해 $i$번 집과 $i + 1$번 집이 도로로 연결되어 있고, 1번 집과 $2N$번 집이 도로로 연결되어 있다.
뜨룹랜드에는 1번부터 $N$번까지 번호가 매겨진 $N$명의 사람들이 살고 있다. 각 사람은 정확히 2개의 집을 소유하고 있다. 즉 주인이 없는 집은 없다. $i$번 사람이 소유한 두 집의 번호를 $x_i$, $y_i$라 하자.
뜨룹랜드에 다음 조건을 만족하도록 정확히 $2N-3$개의 양방향 도로를 더 지으려고 한다.
- 도로는 서로 다른 두 집을 선분으로 연결해야 한다.
- 이미 지어져 있는 도로를 포함하여, 같은 쌍을 잇는 도로는 2개 이상 있을 수 없다.
- 두 도로는 양쪽 끝이 아닌 지점에서 교차할 수 없다.
$a$번 집에서 $b$번 집으로 갈 때 거쳐야 하는 최소 도로 개수를 $Dist(a, b)$라 할 때, 위 조건을 만족하면서 $\sum_{i=1}^{N} {Dist(x_i, y_i)}$가 최소가 되도록 하는 도로 배치를 구하여라.
입력
첫째 줄에 $N$($2 \leq N \leq 200\ 000$) 이 주어진다.
그 후 $N$개의 줄에 $i$번 사람이 소유한 두 집의 번호인 $x_i$, $y_i$가 공백을 사이에 두고 주어진다. ($1 \leq x_i, y_i \leq 2N$)
출력
첫째 줄에 $\sum_{i=1}^{N} {Dist(x_i, y_i)}$의 최솟값을 출력한다.
그 후 $2N-3$개의 줄에 새로 지을 도로가 잇는 두 집의 번호를 공백을 사이에 두고 출력한다.
가능한 배치가 여러 가지라면 아무것이나 출력해도 된다.
예제 입력 1
3 1 3 2 5 6 4
예제 출력 1
5 1 3 1 4 6 4
노트
그림 B.1: 예제 1에 대해 정답으로 가능한 도로 배치 중 하나
$Dist(1, 3)$ = 1, $Dist(4, 6)$ = 1, $Dist(2, 5)$ = 3 이므로 합은 5이다. 합을 4 이하로 만들 수 없으므로 해당 배치를 출력한다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호