まず、状況を整理すると、ある点Pを1点定めて、そこから「指定されたN点のマンハッタン距離の2倍からPから最遠の点までのマンハッタン距離を引いたもの」を最小化する問題です。(点Pは明らかに点が存在する長方領域の中です)
結論から言うと、点集合の各座標をソートしてそれぞれの座標で中央値を取ったもの(ただし、Nが偶数の時は小さいほうからN/2番目の座標か(N/2)+1番目の座標のどちらかを取る)の最大4点のうちのどれかになるので、これを(幾何的に)証明します。
(以降、マンハッタン距離1回分しか考慮されない最遠の点を「弾かれる最遠の点」と表現します)
まず、最適な点Pが最大2つの中央値に囲まれた長方領域上に含まれることを示します。これは1次元上に落として考えると考えやすいです。
次に、最適な点は中央値同士で囲まれた長方領域の四隅のどれかになることを示します。これは目標と同値です。
ここで、ある点を通る2直線 y=x+C,y=-x+C(Cは定数)を使って議論します。
よって証明出来ました。(図証中心ですみません…)
あとは実装をすれば通ります。
https://atcoder.jp/contests/joi2011ho/submissions/4835990
