JOIうめ レベル8 (その3)

JOI11,12更新予定

JOI 11予選

問題は

歩くサンタクロース

概要

H*Wのマスにいくつか家がある。
サンタクロースはまずスタート地点を決める。その後、以下の行動をとる。
・家に訪れスタート地点に戻る。
・最後に訪れる家がゴール
サンタクロースは格子状にのみ移動する（マンハッタン距離）
この時サンタクロースの移動距離の最小値とそれを達成するときのスタート地点を求めよ。

H,W<=10^9,家の個数<=10^5

解法

マンハッタン距離なのでx軸とy軸を一度別々に考える。
また、最後に訪れる家は一度除外して考えると、スタート地点と各家の座標の差の和を最小にする問題となり、これは座標の中央値を選ぶことで最小値が達成できる。したがって、x軸、y軸の中央値をとると良い。
最後に除外した家について考える。中央値より一つ小さい点、一つ大きい点のどれかが最終的な座標になるため、これら(高々9点)に対して移動距離の最小値を計算する（距離の総和*2-最も遠い家の距離)。

実装

とくに。

感想

最初厳密解を求めようとして場合分けが煩雑になりそうになったが定数倍が多少伸びても問題ない。よく忘れる。