上海市计算机学会-最远城市距离

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

|x-x'|+|y-y'|

给定 n 个点的坐标，请从中寻找两个点，使得它们的城市距离达到最大，并输出这个最大值

我们先来看任意两点的曼哈顿距离公式：

绝对值意味着里面的值可正可负。所以，接下来我们要分类讨论。

在下面的式子中，(x,y)(x,y)为平面上一点，(x',y')(x′,y′)为平面上另一点。我们可以对原式变形：

1.两个绝对值内都是正数：x1-x2+y1-y2=> (x1+y1)-(x2+y2)

2.两个绝对值内都是负数：x2-x1+y2-y1=>(x2+y2)-(x1+y1)

3.一正一负：x1-x2+y2-y1=(x1-y1)-(x2-y2)

4.一负一正: x2-x1+y1-y2=(x2-y2)-(x1-y1)

要想城市最大，就 x+y最大，x+y最小；x-y最大，最小值；之后根据之前写的1，2，3，4找

max{（x+y最大-x+y最小），（x-y最大-x-y最小）}

n=int(input())
x=[]
y=[]
for i in range(n):
    a,b=list(map(int,input().split()))
    x.append(a)
    y.append(b)
maxplus=-10000000000
minplus=10000000000
maxminus=-10000000000
minminus=10000000000

for i in range(n):
    maxplus=max(maxplus,x[i]+y[i])
    minplus=min(minplus,x[i]+y[i])
    maxminus=max(maxminus,x[i]-y[i])
    minminus=min(minminus,x[i]-y[i])

print(max(maxplus-minplus,maxminus-minminus))

超时了，不过超过60分以后了编辑推荐的优秀解答。 意识到是不需要读取数据到列表里，动态思维来读取即可。

以后我也多用c++来试试！

#include 
#include 
using namespace std;

int n,x,y,addmax,addmin=2e9,submax,submin=2e9;

int main() {
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> x >> y;
        addmax=max(addmax,x+y);
        addmin=min(addmin,x+y);
        submax=max(submax,x-y);
        submin=min(submin,x-y);
    }
    cout << max(addmax-addmin,submax-submin);
    //简单易懂的代码
}