問題一覧 > 通常問題

No.1998 Manhattan Restaurant

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : MasKoaTSMasKoaTS / テスター : colognecologne potato167potato167
3 ProblemId : 7915 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-17 23:45:40

問題文

二次元平面上に $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$ つの小課題によって区分されています。

  1. $N \leq 600$ (上から $15$ 番目のテストケースまで)

  2. 追加の制約はない

提出された解答については、小課題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もしくは右上の雲マークをクリックしてアカウントを作成してください。