問題一覧 > 通常問題

No.2436 Min Diff Distance

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : cho435cho435 / テスター : ebi_flyebi_fly shobonvipshobonvip noya2noya2 👑 potato167potato167
3 ProblemId : 10009 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-15 00:32:10

問題文

二次元平面上に $N$ 個の点があります。 $i$ 番目の点の座標は $(X_i, Y_i)$ です。

$1 \leq i \leq N$ に対し、 $P_i$ を $i$ 番目の点とその他の点とのマンハッタン距離の最大値と最小値の差の絶対値とします。

$P_i$ の最小値、つまり、 $ \min(P_1,P_2,\dots,P_N) $ を求めてください。

ただし、 $i$ 番目の点と $j$ 番目の点のマンハッタン距離は $ |X_i - X_j| + |Y_i - Y_j| $ であるとします。

制約

  • $ 2 \leq N \leq 2 \times 10^5 $
  • $ 1 \leq X_i, Y_i \leq N $
  • $ (X_i, Y_i) \neq (X_j, Y_j)\ (i \neq j) $
  • 入力はすべて整数

入力

$N$
$X_1\ Y_1$
$X_2\ Y_2$
$\vdots$
$X_N\ Y_N$

出力

$P_i$ の最小値を出力してください。

サンプル

サンプル1
入力
4
1 1
1 2
3 2
4 4
出力
1

それぞれの $P_i$ の値は $(5,4,1,3)$ であるので、最小である $1$ を出力します。

サンプル2
入力
3
1 1
2 2
3 3
出力
0

サンプル3
入力
12
1 1
5 7
5 4
9 9
10 5
2 11
6 1
9 2
1 9
4 11
11 12
9 5
出力
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。