102155: [AtCoder]ABC215 F - Dist Max 2

Problem Statement

Given are $N$ distinct points in a two-dimensional plane. Point $i$ $(1 \leq i \leq N)$ has the coordinates $(x_i,y_i)$.

Let us define the distance between two points $i$ and $j$ be $\mathrm{min} (|x_i-x_j|,|y_i-y_j|)$: the smaller of the difference in the $x$-coordinates and the difference in the $y$-coordinates.

Find the maximum distance between two different points.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

Output

Print the maximum distance between two different points.

Sample Input 1

3
0 3
3 1
4 10

Sample Output 1

4

The distances between Points $1$ and $2$, between Points $1$ and $3$, and between Points $2$ and $3$ are $2$, $4$, and $1$, respectively, so your output should be $4$.

Sample Input 2

4
0 1
0 4
0 10
0 6

Sample Output 2

0

Sample Input 3

8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

Sample Output 3

801

问题描述

在二维平面上给出了N个不同的点。点i $(1 \leq i \leq N)$的坐标为$(x_i,y_i)$。

定义两点i和j之间的距离为$\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