H - 空港
解説
/
すぬけ君は、空港を N 個持っている。i 番目の空港の座標は (x_i, y_i) である。すぬけ君は、あまり近い空港の間に飛行機を飛ばしても意味がないので、マンハッタン距離 ((x_1, y_1) と (x_2, y_2) のマンハッタン距離は |x_1 - x_2| + |y_1 - y_2|) が X 以上である全ての空港のペアの間に飛行機を飛ばすことにした。どの空港からどの空港へも飛行機だけを使っていけるようになる最大の X を求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
Constraints
- 2 \leq N \leq 100000
- 0 \leq x_i, y_i \leq 10^9
- 二つの空港が同じ座標にあることはない。
Input Format
N x_1 y_1 : x_N y_N
Output Format
Sample Input 1
6 1 7 8 5 6 3 10 3 5 2 6 10
Sample Output 1
9