問題一覧 > 通常問題

No.2612 Close the Distance

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
5 ProblemId : 9734 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-01-17 09:04:20

問題文

二次元平面上に $N$ 点があり、 $i$ 番目の点は座標 $\left( x_i, y_i \right)$ にあります。ここで、全ての点は異なる位置にあります。
あなたは、 $N$ 点の各点を色 $1,2,3$ のいずれかで塗り分けます。ここで、塗り分けに対する 微妙さ を以下のように定義します。

  • 同じ色で塗られた $2$ 点のペアについて、その $2$ 点間のマンハッタン距離としてありえる最大値。ただし、同じ色で塗られた $2$ 点のペアが存在しない場合は $0$ とします。
    • ただし、 $2$ 点 $P_1(i_1,j_1),P_2(i_2,j_2)$ に対し $P_1$ と $P_2$ 間のマンハッタン距離を $|i_1-i_2|+|j_1-j_2|$ とします。

微妙さ が最小となるように塗り分けたときの 微妙さ を求めてください。

入力

$N$
$x_1\ \ y_1$
$x_2\ \ y_2$
$\vdots$
$x_N\ \ y_N$

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq x_i,y_i \leq 10^9$ $\left( 1 \leq i \leq N \right)$
  • $\left( x_i,y_i \right) \neq \left( x_j,y_j \right)$ $\left( i \neq j \right)$
  • 入力は全て整数

出力

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

サンプル

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

例えば、 $1$ 番目の点を色 $1$ で、 $2,5$ 番目の点を色 $2$ で、 $3,4$ 番目の点を色 $3$ で塗れば良いです。
微妙さ を $1$ 以下にはできないことが証明できるので、答えは $2$ です。

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

すべての点を違う色で塗り分ければよいです。

サンプル3
入力
10
57 71
29 39
46 32
85 19
34 57
79 13
60 72
55 46
79 12
13 18
出力
47

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