2274: 最远城市距离

Memory Limit:128 MB Time Limit:1.000 S
Creator:
Submit:22 Solved:7

Description

大城市的道路是相互平行或垂直的,如果在城市的道路上行走,不能用点与点之间的直线距离计算长度,而是应该定义两个点(设坐标分别为 (x,y)与 (x',y'))的城市距离为:

|x-x'|+|y-y'|;给定 n 个点的坐标,请从中寻找两个点,使得它们的城市距离达到最大,并输出这个最大值。

Input

第一行:单个整数 n
第二行到第 n+1行:每行有两个整数 xi 和 yi,表示一个点的坐标。

Output

单个整数:表示最大的城市距离。

Sample Input

4
0 0
0 1
1 3
3 2

Sample Output

5

HINT

(0,0)与(3,2)的城市距离是最大的



数据范围: 
  • 对于 30% 的数据,2n5,000
  • 对于 60% 的数据,2n50,000
  • 对于 100% 的数据,2n500,000
  • 500,000,000xi,yi500,000,000