分数: 400 点
问题陈述
有 N 房屋编号 1 通过 N 在二维平面上。 房子 i 位于 (x_i, y_i).
我们使用切比雪夫距离来计算两栋房子之间的距离。也就是房屋之间的距离 i 和 j is \max(|x_i - x_j|, |y_i-y_j|).
有 \frac{N(N-1)}{2} 由两个不同的房子组成的对。对于每一对,我们将计算房屋之间的距离,然后对这些距离进行排序 降序排列 获取长度序列 \frac{N(N-1)}{2}。从该序列的开头查找第二个值。
约束
- 输入中的所有值都是整数。
- 3 \leq N \leq 2 \times 10^{5}
- -10^{9} \leq x_i, y_i \leq 10^{9}
输入
输入由标准输入按以下格式给出:
N
x_{1} y_{1}
\vdots
x_{N} y_{N}
输出
打印按降序排列的不同房屋距离序列开头的第二个值。
示例输入 1
3 0 0 1 2 4 0
示例输出 1
3
- 房屋之间的距离 1 和 2 is 2;
- 房屋之间的距离 1 和 3 is 4;
- 房屋之间的距离 2 和 3 is 3.
- 通过按降序对这些进行排序,我们得到 (4,3,2),其中从开头算起的第二个值是 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