分数: 500 点
问题陈述
给出的是 N 二维平面中的不同点。点 i (1 \leq i \leq N) 有坐标 (x_i,y_i).
让我们定义两点之间的距离 i 和 j be \mathrm{min} (|x_i-x_j|,|y_i-y_j|): 差异较小者 x- 坐标和差异 y- 坐标。
查找两个不同点之间的最大距离。
约束
- 2 \leq N \leq 200000
- 0 \leq x_i,y_i \leq 10^9
- (x_i,y_i) \neq (x_j,y_j) (i \neq j)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N x_1 y_1 x_2 y_2 \vdots x_N y_N
输出
打印两个不同点之间的最大距离。
示例输入 1
3 0 3 3 1 4 10
示例输出 1
4
点之间的距离 1 和 2,点之间 1 和 3,以及点之间 2 和 3 是 2, 4,和 1分别,所以你的输出应该是 4.
示例输入 2
4 0 1 0 4 0 10 0 6
示例输出 2
0
示例输入 3
8 897 729 802 969 765 184 992 887 1 104 521 641 220 909 380 378
示例输出 3
801