Dist Max SOLUTION AtCoder Contest 178

Dist Max SOLUTION

Problem Statement
There are N points on the 2D plane, i-th of which is located on (xi,yi). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?
Here, the Manhattan distance between two points (xi,yi) and (xj,yj) is defined by |xi−xj|+|yi−yj|.
Constraints
2≤N≤2×105
1≤xi,yi≤109
All values in input are integers.
Input
Input is given from Standard Input in the following format: N
x1
y1
x2
y2
:
xN
yN
Output
Print the answer.
Sample Input 1
Copy
3
1 1
2 4
3 2
Sample Output 1
Copy
4
The Manhattan distance between the first point and the second point is
|1−2|+|1−4|=4, which is maximum possible.
Sample Input 2
Copy
2
1 1
1 1
Sample Output 2
Copy
0

Leave a Comment

close
error: Content is protected !!