Farthest by Manhattan

Difficulty: 1600 3500 ms 128 MB

math geometry

Print the maximum Manhattan distance |x_i−x_j| + |y_i−y_j| over all point pairs.

Input: the first line has N (N ≥ 2); the next N lines each have x y.

Output: the maximum pairwise Manhattan distance.

Constraints:

• 2 ≤ N ≤ 10⁵
• |coordinates| ≤ 10⁶

Sample Tests

3
0 0
2 3
-1 1

5

2
0 0
1 1

2

Read the Editorial