No.1998 Manhattan Restaurant
タグ : / 解いたユーザー数 33
作問者 :
MasKoaTS
/ テスター :
👑 
potato167
問題文
二次元平面上に $1, 2, \dots, N$ の番号が付いた $N$ 軒の民家があり、民家 $i$ $(1 \leq i \leq N)$
の座標は $( X_{i}, Y_{i} )$ です。
ただし、$X_{i}, Y_{i}$ はどちらも偶数とします。
コアさんは、この平面上の好きな場所を自由に $2$ 箇所選び、それぞれに飲食店を建設することにしました。
民家 $i$ $(1 \leq i \leq N)$ から $2$ 箇所の飲食店までのマンハッタン距離のうち小さい方の値を $d_{i}$ とするとき、
$\max ( d_{1}, d_{2}, \dots, d_{N} )$ の値としてあり得るものの最小値を求めてください。
なお、本問の制約下において、答えは必ず整数となることが保証されます。
「マンハッタン距離」の定義（クリックで展開）
二次元平面上の任意の $2$ 点 $P_{1} ( x_{1}, y_{1} )$, $P_{2} ( x_{2}, y_{2} )$ について、
これら $2$ 点間のマンハッタン距離 $L^{1} (P_{1}, P_{2} )$ は次のように定義されます。
$L^{1} (P_{1}, P_{2} ) := | x_{1} - x_{2} | + | y_{1} - y_{2} | $
制約
$1 \leq N \leq 10^{5}$
$N$ は整数
$-10^{9} \leq X_{i}, Y_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
$X_{i}$, $Y_{i}$ $(1 \leq i \leq N)$ は偶数
小課題
yukicoderの仕様上、本問に部分点は設定されていませんが、
本問のテストケース（入力）は次の $2$ つの小課題によって区分されています。
$N \leq 600$ （上から $15$ 番目のテストケースまで）
追加の制約はない
提出された解答については、小課題1・小課題2ともに正解である場合にのみ AC と判定されます。
小課題1・小課題2のうち少なくとも一方で不正解である場合には AC と判定されませんので、予めご了承ください。
入力
入力は次の形式で与えられます。
$N$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
$\vdots$
$X_{N}$ $Y_{N}$
$1$ 行目には $N$ が与えられる
$(1 + i)$ $(1 \leq i \leq N)$ 行目には $X_{i}$ と $Y_{i}$ がこの順に半角スペース区切りで与えられる
出力
答えを $1$ 行に出力し、最後に改行してください。
サンプル
サンプル1
入力
3 2 6 -16 20 0 -2
出力
5
例えば、$2$ 軒の飲食店をそれぞれ座標 $(1,2)$, $(-16,20)$ に建設すれば良いです。
この場合、
$d_{1} = \min ( | 2 - 1 | + | 6 - 2 |, | 2 - (-16) | + | 6 - 20 | ) = 5$,
$d_{2} = \min ( | -16 - 1 | + | 20 - 2 |, | -16 - (-16) | + | -20 - (-20) | ) = 0$,
$d_{3} = \min ( | 0 - 1 | + | -2 - 2 |, | 0 - (-16) | + | -2 - 20 | ) = 5$
であり、$\max( d_{1}, d_{2}, d_{3} ) = 5$ です。
$\max( d_{1}, d_{2}, d_{3} )$ の値をこれより小さくすることはできないので、答えは $5$ となります。
既に民家が存在する座標に飲食店を建設しても構いません。
サンプル2
入力
10 0 12 0 2 4 4 0 12 0 2 0 2 2 0 4 8 0 4 0 8
出力
4
複数の民家が同じ座標に存在する場合もあります。
サンプル3
入力
1 100 100
出力
0
サンプル4
入力
10 826 -42644 328 6 620390134 -10369824 -28 305164020 -222219018 -3308 406 467945990 1051026 165620000 178174 -38 -28875428 -515082 -73139174 -121760098
出力
345084361
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。