Khoảng cách Manhattan lớn nhất

Xem dạng PDF

Gửi bài giải

Điểm: 0,10 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài

Đây là phiên bản khó hơn của bài PA094. Điểm khác biệt duy nhất giữa hai bài là giới hạn của ~n~ và đầu vào/ra dữ liệu.

Cho ~n~ điểm trên mặt phẳng Descartes, điểm ~A_i~ có toạ độ ~(x_i, y_i)~. Hãy tìm khoảng cách Manhattan lớn nhất giữa hai điểm bất kỳ trong ~n~ điểm đã cho.

Khoảng cách Manhattan giữa hai điểm ~A(x_A, y_A)~ và ~B(x_B, y_B)~ có giá trị là ~|x_A - x_B| + |y_A - y_B|~.

Input

  • Dòng đầu tiên chứa số nguyên dương ~n~ - số lượng điểm (~2 \leq n \leq 10^5~).
  • ~n~ dòng tiếp theo, một dòng chứa hai số nguyên ~x_i~ và ~y_i~ mô tả toạ độ của điểm ~A_i~ (~|x_i|, |y_i| \leq 10^9~).

Output

In ra khoảng cách Manhattan lớn nhất tìm được.

Sample Test

Input:

5
1 2
2 3
4 4
0 -1
-1 4

Output:

9

Note: Khoảng cách giữa điểm ~A_3~ và ~A_4~ bằng ~9~ là khoảng cách lớn nhất.

CoolImage