← 返回题目列表

AtCoder · abc215_f

I. 距离最大 2

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

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