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.