Walking Santa

Time Limit : 8 sec, Memory Limit : 65536 KB

歩くサンタクロース(Walking Santa)

昨年末,サンタクロースはJOI 村の子供たちにクリスマスプレゼントを渡すのを忘れてしまった.そこで,お詫びの気持ちとして子供たちにチョコレートケーキを届けることにした.届けるべき日は明日に迫っているので,そろそろ移動計画を考えなければならない.

JOI 村は,南北方向にまっすぐに伸びるW 本の道路と,東西方向にまっすぐに伸びるH 本の道路により,碁盤の目の形に区分けされている. 南北方向のW 本の道路には,西から順に1, 2, ... , W の番号が付けられており,東西方向のH 本の道路には,南から順に1, 2, ... , H の番号が付けられている. 西からx 番目の南北方向の道路と,南からy 番目の東西方向の道路が交わる交差点を(x, y) で表す. JOI 村にはN 軒の家があり,それらはいずれかの交差点に位置している. サンタクロースは道路に沿ってのみ移動することができる. 隣り合う交差点の間を移動するのにかかる時間を1 とする.

JOI 村のすべての家には子供がいるので,サンタクロースはJOI 村のすべての家に1 個ずつチョコレートケーキを届けてまわらなければならない. 大切なチョコレートケーキを持ってトナカイと空を飛びまわるのはやや危険であるので,サンタクロースとトナカイはJOI 村のいずれかの交差点に降り立ち,サンタクロースがそこから歩いてチョコレートケーキを届けることにした. サンタクロースは同時に2 個以上のチョコレートケーキを運んで歩くことはしない.つまり,サンタクロースはチョコレートケーキを1 軒の家に届けるたびに降り立った交差点に戻る.

サンタクロースは,JOI 村に降り立ってからすべての家にチョコレートケーキを届けるまでの所要時間が最小になるような移動計画を選ぶことにした.ここで,最後の家にチョコレートケーキを届けてから降り立った交差点に戻るまでの時間は所要時間に含めないことに注意せよ.また,移動にかかる時間以外は考えない.

課題

家の位置の情報が与えられたとき,サンタクロースが降り立つ交差点をうまく選んだ場合の,JOI 村に降り立ってからすべての家にチョコレートケーキを届けるまでの所要時間の最小値と,所要時間を最小にするために降り立つべき交差点の位置を求めるプログラムを作成せよ.

制限

1 ≤ W ≤ 1000000000 = 109    南北方向に伸びる道路の本数
1 ≤ H ≤ 1000000000 = 109    東西方向に伸びる道路の本数
1 ≤ N ≤ 100000 = 105    家の数
1 ≤ XiW    i 番目の家の位置の, 南北方向に伸びる道路の番号
1 ≤ YiH    i 番目の家の位置の, 東西方向に伸びる道路の番号

入力

標準入力から以下の入力を読み込め.

  • 1 行目には各方向の道路の本数を表す整数 W, H が空白を区切りとして書かれている.
  • 2 行目には家の数を表す整数N が書かれている.
  • 続くN 行には,家の位置の情報が書かれている.i + 2 行目(1 ≤ iN) には整数Xi, Yi が空白を区切りとして書かれており,i 番目の家が交差点(Xi, Yi) に位置していることを表す.これらN 個の交差点はすべて異なる.

出力

標準出力に以下のデータを出力せよ.

  • 1 行目には所要時間の最小値を表す1 つの整数が書かれていなければならない.
  • 2 行目には所要時間を最小にするために降り立つべき交差点が(x, y) であるとき,2 つの整数x, y がこの順に空白を区切りとして書かれていなければならない.適切な交差点が複数ある場合は,そのうち最も西にある(つまり,x の値が小さい) 交差点を, それでも1 つに定まらない場合は, さらにそのうちで最も南にある(つまり,y の値が小さい) 交差点を選べ.

注意

この問題では,扱う整数の範囲が32 ビットに収まらない可能性があることに注意せよ.

採点基準

採点用データのうち,配点の40%分については,N ≤ 1000 を満たす.
採点用データのうち,配点の10%分については,W ≤ 50, H ≤ 50, N ≤ 1000 を満たす.

入出力の例

入力例1

5 4
3
1 1
3 4
5 3

出力例1

10
3 3

たとえば,次のような移動計画により所要時間を最小にできる.

  • 交差点(3; 3) に降り立つ.
  • 交差点(3; 4) に位置している家にチョコレートケーキを届ける.ここまでの経過時間は1 である.
  • 交差点(3; 3) に戻る.ここまでの経過時間は2 である.
  • 交差点(5; 3) に位置している家にチョコレートケーキを届ける.ここまでの経過時間は4 である.
  • 交差点(3; 3) に戻る.ここまでの経過時間は6 である.
  • 交差点(1; 1) に位置している家にチョコレートケーキを届ける.ここまでの経過時間は10 である.

入力例2

4 6
8
1 3
3 2
4 4
2 5
2 3
3 3
3 4
2 4

出力例2

21
2 3

家がある交差点に降り立ってもよいことに注意せよ.

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。


Source: 10th Japanese Olympiad in Informatics , 2011-2-13
http://www.ioi-jp.org/