/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2 次元平面上の N 個の相異なる点が与えられます。点 i\, (1 \leq i \leq N) の座標は (x_i,y_i) です。
2 つの点 i,j\, (1 \leq i,j \leq N) の距離を \mathrm{min} (|x_i-x_j|,|y_i-y_j|) 、すなわち x 座標の差と y 座標の差の小さい方と定義します。
異なる 2 つの点の距離の最大値を求めてください。
制約
- 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
出力
異なる 2 つの点の距離の最大値を出力せよ。
入力例 1
3 0 3 3 1 4 10
出力例 1
4
点 1 と点 2 の距離は 2 、点 1 と点 3 の距離は 4 、点 2 と点 3 の距離は 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
Score : 500 points
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