题解：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 i$ $≥$ $x j$ 且 $y i$ $≥$ $y j$ 时， $∣x i −x j ∣+∣y i −y j ∣$ $=$ $(x i −x j )+(y i −y j )$ $=$ $(x i +y i )−(x j +y j )$
当 $x i$ $≥$ $x j$ 且 $y i$ $<$ $y j$ 时， $∣x i −x j ∣+∣y i −y j ∣$ $=$ $(x i −x j )+(y j −y i )$ $=$ $(x i −y i )−(x j −y j )$ 。
当 $x i$ $<$ $x j$ 且 $y i$ $≥$ $y j$ 时， $∣x i −x j ∣+∣y i −y j ∣$ $=$ $(x j −x i )+(y i −y j )$ $=$ $(−x i +y i )−(−x j +y j )$ 。
当 $x i$ $<$ $x j$ 且 $y i$ $<$ $y j$ 时， $∣x i −x j ∣+∣y i −y j ∣$ $=$ $(x j −x i )+(y j −y i )$ $=$ $(−x i −y i )−(−x j −y j )$

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

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

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

code:

CPP

#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;
}

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

文章操作

相关推荐

评论

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