← 返回题目列表

AtCoder · arc121_a

A. 第二大距离

中文机器翻译题面 查看原题

分数: 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