문제
'푸른 바다가 끝없이 펼쳐진 광경, 그 위에 수없이 떠있는 보석같은 섬들.'
여름 휴양지로 유명한 한컴해에 오신 여러분을 환영합니다.
한컴해는 2500 x 2500 칸의 격자로 표현되는 넓은 바다입니다.
바다의 해역은 북에서 남으로 행에 1~2500의 번호를, 서에서 동으로 열에 1~2500의 번호를 부여해 칸 단위의 좌표로 구분합니다.
한컴해에는 총 N개의 섬이 있으며 하나의 섬은 정확히 한 칸의 해역을 차지합니다.
같은 좌표를 공유하는 두 섬은 없습니다.
한컴해에 관광 오셨다면 꼭 요트 체험을 해보셔야 합니다.
한컴해에는 항상 북서쪽에서 남동쪽으로 강한 바람이 붑니다.
여러분은 요트를 타고 한 섬에서 출발하면 북서쪽, 혹은 남동쪽에 있는 섬으로 갈 수 있습니다.
보다 정확히 말하면, 출발한 섬보다 행과 열의 번호가 둘 다 크거나 둘 다 작은 섬으로 이동 가능합니다.
한컴해의 섬들은 항상 직접은 아니더라도 몇 개의 섬을 거쳐 어떤 두 섬 사이라도 이동할 수 있습니다.
두 섬 사이의 항해 거리는 한 섬에서 다른 섬으로 이동하기 위해 필요한 최소의 요트 항해 횟수로 정의합니다.
직접 항해 가능하면 1, 한 섬을 경유해서 갈 수 있으면 2와 같은 식으로 정의됩니다.
요트 체험을 하고 싶다면 시작할 섬으로 어디가 좋을지 한 번 알아보세요.
한컴 해의 지도를 드릴테니, 지도의 각 섬마다 다른 모든 섬과의 항해 거리의 합을 구해보세요.
문제를 빠르게 해결하고 요트를 즐기셨으면 좋겠네요.
모쪼록 즐거운 여행 되시길 바랍니다.
입력
첫 줄에 N이 주어진다. (1 <= N <= 250,000)
이후 N줄에 걸쳐 한 줄에 하나씩 섬의 좌표가 주어진다. (좌표 범위 = 1~2,500)
출력
N줄에 걸쳐 입력에 주어진 것과 동일한 순서로 각 섬과 나머지 섬들 사이의 항해 거리의 합을 출력하라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | N <= 100 |
| #2 | 7점 | N <= 1,500 |
| #3 | 13점 | N <= 5,000 |
| #4 | 19점 | N <= 25,000 |
| #5 | 41점 | 추가적인 제약 조건이 없음 |
예제 #1
7
1 7
7 5
4 5
4 8
6 6
6 1
2 3
16
11
12
11
12
16
8
예제 #2
4
1 1
2 3
3 2
4 4
3
4
4
3
로그인해야 코드를 작성할 수 있어요.