問題一覧 > 通常問題

No.1998 Manhattan Restaurant

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

問題文

二次元平面上に 1,2,,N1, 2, \dots, N の番号が付いた NN 軒の民家があり、民家 ii (1iN)(1 \leq i \leq N) の座標は (Xi,Yi)( X_{i}, Y_{i} ) です。
ただし、Xi,YiX_{i}, Y_{i} はどちらも偶数とします。

コアさんは、この平面上の好きな場所を自由に 22 箇所選び、それぞれに飲食店を建設することにしました。

民家 ii (1iN)(1 \leq i \leq N) から 22 箇所の飲食店までのマンハッタン距離のうち小さい方の値を did_{i} とするとき、
max(d1,d2,,dN)\max ( d_{1}, d_{2}, \dots, d_{N} ) の値としてあり得るものの最小値を求めてください。

なお、本問の制約下において、答えは必ず整数となることが保証されます。

「マンハッタン距離」の定義(クリックで展開)

二次元平面上の任意の 22P1(x1,y1)P_{1} ( x_{1}, y_{1} ), P2(x2,y2)P_{2} ( x_{2}, y_{2} ) について、
これら 22 点間のマンハッタン距離 L1(P1,P2)L^{1} (P_{1}, P_{2} ) は次のように定義されます。

  • L1(P1,P2):=x1x2+y1y2L^{1} (P_{1}, P_{2} ) := | x_{1} - x_{2} | + | y_{1} - y_{2} |

制約

  • 1N1051 \leq N \leq 10^{5}

  • NN は整数

  • 109Xi,Yi109-10^{9} \leq X_{i}, Y_{i} \leq 10^{9} (1iN)(1 \leq i \leq N)

  • XiX_{i}, YiY_{i} (1iN)(1 \leq i \leq N)偶数

小課題

yukicoderの仕様上、本問に部分点は設定されていませんが、
本問のテストケース(入力)は次の 22 つの小課題によって区分されています。

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

  2. 追加の制約はない

提出された解答については、小課題1・小課題2ともに正解である場合にのみ AC と判定されます。

小課題1・小課題2のうち少なくとも一方で不正解である場合には AC と判定されませんので、予めご了承ください。

入力

入力は次の形式で与えられます。

NN
X1X_{1} Y1Y_{1}
X2X_{2} Y2Y_{2}
   \vdots
XNX_{N} YNY_{N}
  • 11 行目には NN が与えられる

  • (1+i)(1 + i) (1iN)(1 \leq i \leq N) 行目には XiX_{i}YiY_{i} がこの順に半角スペース区切りで与えられる

出力

答えを 11 行に出力し、最後に改行してください。

サンプル

サンプル1
入力
3
2 6
-16 20
0 -2
出力
5

例えば、22 軒の飲食店をそれぞれ座標 (1,2)(1,2), (16,20)(-16,20) に建設すれば良いです。

この場合、

d1=min(21+62,2(16)+620)=5d_{1} = \min ( | 2 - 1 | + | 6 - 2 |, | 2 - (-16) | + | 6 - 20 | ) = 5,

d2=min(161+202,16(16)+20(20))=0d_{2} = \min ( | -16 - 1 | + | 20 - 2 |, | -16 - (-16) | + | -20 - (-20) | ) = 0,

d3=min(01+22,0(16)+220)=5d_{3} = \min ( | 0 - 1 | + | -2 - 2 |, | 0 - (-16) | + | -2 - 20 | ) = 5

であり、max(d1,d2,d3)=5\max( d_{1}, d_{2}, d_{3} ) = 5 です。

max(d1,d2,d3)\max( d_{1}, d_{2}, d_{3} ) の値をこれより小さくすることはできないので、答えは 55 となります。

既に民家が存在する座標に飲食店を建設しても構いません。

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。