문제
JOI 군은 엄청나게 큰 책상과 동전들을 갖고 있다.
책상 여기저기에 놓여 있는 동전들을 가지런히 정리하려고 한다.
책상은 2,000,000,001 * 2,000,000,001 크기의 격자로 이루어져 있다.
행은 아래부터 위까지 –1,000,000,000 ~ 1,000,000,000의 번호가 매겨져 있다.
열 또한 왼쪽부터 오른쪽까지 –1,000,000,000 ~ 1,000,000,000의 번호가 매겨져 있다.
x번 행과 y번 열에 해당하는 칸을 (x, y)로 나타내자.
책상 위에는 2N개의 동전이 있다. i번째(1≤i≤2N) 동전은 (Xi, Yi) 칸에 있다.
JOI 군의 목표는 1≤x≤N, 1≤y≤2인 모든 (x, y) 칸에 동전이 하나씩 있게 하는 것이다.
동전을 옮길 때는 동전 하나를 골라 인접한 칸으로 이동시키는 것을 반복한다.
서로 변을 공유하는 두 칸을 인접하다고 한다. 여러 동전이 한 칸에 있을 수도 있다.
JOI군이 목표를 이루기 위해 해야 하는 동전 이동 횟수의 최솟값을 출력하여라.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 그 후 2N개의 줄에 동전의 좌표 Xi, Yi가 주어진다. (-1,000,000,000 ≤ Xi,Yi ≤ 1,000,000,000)
출력
JOI군이 목표를 이루기 위해 해야 하는 동전 이동 횟수의 최솟값을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 8점 | |
| #2 | 29점 | |
| #3 | 63점 | 추가적인 제한 조건이 없다. |
예제 #1
3
0 0
0 4
4 0
2 1
2 5
-1 1
15
동전의 위치는 다음과 같다.
JOI 군이 목표를 이루기 위해 하는 15번의 연산의 예시는 아래와 같다.
첫 번째 동전을 (0,0) -> (1,0) -> (1,1) -> (1,2)로 이동시킨다.
두 번째 동전을 (0,4) -> (1,4) -> (1,3) -> (2,3) -> (3,3) -> (3,2)로 이동시킨다.
세 번째 동전을 (4,0) -> (4,1) -> (3,1)로 이동시킨다.
네 번째 동전은 가만히 둔다.
다섯 번째 동전을 (2,5) -> (2,4) -> (2,3) -> (2,2)로 이동시킨다.
여섯 번째 동전을 (-1,1) -> (0,1) -> (1,1)로 이동시킨다.
14번의 연산으로는 목표를 이룰 수 없으므로 15를 출력한다.
예제 #2
4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1
9
예제 #3
5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3
8000000029
로그인해야 코드를 작성할 수 있어요.