题解：B4253 [科大国创杯小学组 2024] 几何

· · 题解

题意：

让我们写出欧几里得距离或曼哈顿距离的最大值

思路

30分思路：用两个双层循环暴力，计算欧几里得距离或曼哈顿距离，再取最大值，输出最大值。

缺陷：时间复杂度为 O(n^2) ，1≤n≤10^6 ,会超时，且计算欧几里得距离时，用 sqrt 函数会浮点数误差。

改进：

将 sqrt 替换。

50分思路：

和30分思路没有太大差别，只是把 sqrt 函数改成了* 1LL 。

缺陷：

时间复杂度为 O(n^2) ，会超时。

改进：

把计算曼哈顿距离的函数的时间复杂度降至 O(n) 。

100分思路：

对于曼哈顿距离 ∣x i ​ −x j ​ ∣+∣y i ​ −y j ​ ∣ ，可以根据绝对值的性质进行展开：

因此，我们只需要分别找出

、 (x−y) 、 (−x+y) 、 (−x−y)

的最大值和最小值，然后计算它们之间的最大差值，即可得到最大曼哈顿距离。

code: 
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,op;
int x[N],y[N];
long long maxn=-0x3f3f3f3f;
int main(){
    cin>>n>>op;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    if(op==1){
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                long long road=1LL*(x[i]-x[j])*(x[i]-x[j])+1LL*(y[i]-y[j])*(y[i]-y[j]);
                maxn=max(maxn, road);
            }
        }
    }else{
        long long max1=-1e18,min1=1e18;
        long long max2=-1e18,min2=1e18;
        long long max3=-1e18,min3=1e18;
        long long max4=-1e18,min4=1e18;
        for(int i=1;i<=n;i++){
            max1=max(max1,1LL*x[i]+y[i]);
            min1=min(min1,1LL*x[i]+y[i]);
            max2=max(max2,1LL*x[i]-y[i]);
            min2=min(min2,1LL*x[i]-y[i]);
            max3=max(max3,1LL*(-x[i])+y[i]);
            min3=min(min3,1LL*(-x[i])+y[i]);
            max4=max(max4,1LL*(-x[i])-y[i]);
            min4=min(min4,1LL*(-x[i])-y[i]);
        }
        maxn=max({max1-min1,max2-min2,max3-min3,max4-min4});
    }
    cout<<maxn;
    return 0;
}