레이팅 미적용JOI 氏のコレクションルームには非常に大きな机があり,その上には何枚もの貴重なコインがある.机
の掃除をするために,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 \le x \le N\) かつ\(1 \le y \le 2\) を満たす(x, y) で表される2N 個のマスに,それぞれコインが1 枚ずつ置か
れている状態にすることである.コインを傷つけないようにするため,
「コインを1 枚選び,それが置かれ
ているマスと辺で隣り合ったマスのいずれかに,そのコインを移動させる」という操作のみができる.途
中,複数のコインが同じマスに置かれていてもよい.JOI 氏は,できるだけ少ない回数の操作で目標を達
成したい.
コインの枚数と,現在コインが置かれているマスが与えられたとき,目標を達成するために必要な操作
回数の最小値を求めるプログラムを作成せよ.
• 1 ≦N ≦100 000.
• −1 000 000 000 ≦Xi ≦1 000 000 000 (1 ≦i ≦2N).
• −1 000 000 000 ≦Yi ≦1 000 000 000 (1 ≦i ≦2N).
第18 回日本情報オリンピック(JOI 2018/2019) 本選
2019 年2 月10 日(茨城県つくば市)
- (8 点) \(N \le 10\).
- (29 点) N ≦1 000.
- (63 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
N
X1 Y1
...
X2N Y2N
標準出力に,目標を達成するために必要な操作回数の最小値を1 行で出力せよ.
3
0 0
0 4
4 0
2 1
2 5
-1 1
15
4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1
9
5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3
8000000029