[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$