3115: 最远城市距离
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
大城市的道路是相互平行或垂直的，如果在城市的道路上行走，不能用点与点之间的直线距离计算长度，而是应该定义两个点（设坐标分别为 (�,�)(x,y) 与 (�′,�′)(x′,y′)）的城市距离为
∣�−�′∣+∣�−�′∣∣x−x′∣+∣y−y′∣
给定 �n 个点的坐标，请从中寻找两个点，使得它们的城市距离达到最大，并输出这个最大值。
输入
第一行：单个整数 �n。
第二行到第 �+1n+1 行：每行有两个整数 ��xi 和 ��yi，表示一个点的坐标。
第二行到第 �+1n+1 行：每行有两个整数 ��xi 和 ��yi，表示一个点的坐标。
- 对于 30%30% 的数据，2≤�≤5,0002≤n≤5,000；
- 对于 60%60% 的数据，2≤�≤50,0002≤n≤50,000；
- 对于 100%100% 的数据，2≤�≤500,0002≤n≤500,000。
- −500,000,000≤��,��≤500,000,000−500,000,000≤xi,yi≤500,000,000；
输出
单个整数：表示最大的城市距离。
样例输入 复制
4
0 0
0 1
1 3
3 2样例输出 复制
5提示
(0,0)与(3,2)的城市距离是最大的