题目描述

$2$ 次元平面上に $1$ から $N$ の番号がついた $N$ 軒の家があります。 家 $i$ は $(x_i,y_i)$ にあります。

家同士の距離はチェビシェフ距離で定められます。 すなわち、家 $i,j$ 間の距離は $\max(|x_i\ -\ x_j|,\ |y_i-y_j|)$ です。

異なる $2$ つの家の組は $\frac{N(N-1)}{2}$ 通りあります。異なる家の組それぞれについて家同士の距離を計算し、距離の値を 降順 に並べて長さ $\frac{N(N-1)}{2}$ の数列を作ります。この数列の先頭から $2$ 番目の値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $x_{1}$ $y_{1}$ $\vdots$ $x_{N}$ $y_{N}$

输出格式

異なる家の組全てについて家同士の距離を計算し、降順に並べて数列を作ったときの先頭から $2$ 番目の値を出力せよ。

题目大意

[ARC121A] 2nd Greatest Distance

题目描述

在二维平面上有 $N$ 个使用编号 $1$ 到 $N$ 的数字标记的房子。 房子 $i$ 位于 $(x_i,y_i)$。

房子 $i,j$ 之间的距离是 $\max(\left|{x_i-x_j}\right|, \left|{y_i-y_j}\right|)$。

有总共 $N(N-1)/2$ 对不同的房子，对于每一对不同的房子，计算它们之间的距离，把距离值按降序排列成一个长度为 $N(N-1)/2$ 的数列。请输出这个数列的第二个数字。

输入格式

从标准输入中读入数据，输入格式如下：

$N$ $x_{1}$ $y_{1}$ $\ldots$ $x_{N}$ $y_{N}$

输出格式

对于每一个样例，输出第二大的数字。

样例说明

样例输入 #1

3
0 0
1 2
4 0

样例输出 #1

3

样例输入 #2

4
0 0
0 0
1 0
0 1

样例输出 #2

1

样例输入 #3

20
407 361
167 433
756 388
-551 -47
306 -471
36 928
338 -355
911 852
288 70
-961 -769
-668 -386
-690 -378
182 -609
-677 401
-458 -112
184 -131
-243 888
-163 471
-11 997
119 544

样例输出 #3

1766

提示

• 所有的输入都保证为整数
• $3 \leqslant N \leqslant 2 \times 10^5$
• $-10^9 \leqslant x_i, y_i \leqslant 10^9$

3
0 0
1 2
4 0

3

4
0 0
0 0
1 0
0 1

1

20
407 361
167 433
756 388
-551 -47
306 -471
36 928
338 -355
911 852
288 70
-961 -769
-668 -386
-690 -378
182 -609
-677 401
-458 -112
184 -131
-243 888
-163 471
-11 997
119 544

1766

提示

制約

• 与えられる入力は全て整数
• $3\ \leq\ N\ \leq\ 2\ \times\ 10^{5}$
• $-10^{9}\ \leq\ x_i,\ y_i\ \leq\ 10^{9}$

Sample Explanation 1

- 家 $1,2$ 間の距離は $2$ です。 - 家 $1,3$ 間の距離は $4$ です。 - 家 $2,3$ 間の距離は $3$ です。 - これらを降順に並べて作られる数列は $(4,3,2)$ です。先頭から $2$ 番目に現れる数は $3$ です。

Sample Explanation 2

- 家は同じ座標に存在することもあります。