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

· · 题解

题意

这道题暴力是肯定会 TLE 的，又因为大数据都是求哈曼顿距离的最大值，所以我们可以考虑用数学方法优化。

我们可以维护一下 x-y 和 x+y 的最大最小值，最后输出 x-y 最大值减最小值与 x+y 最大值减最小值的最大值就好了。

具体数学证明我们可以看看这位大佬的博客。

证明

代码

#include<bits/stdc++.h>
#define int long long
#define inf 0x7f7f7f7f
using namespace std;
const int maxn = 1e6 + 100;
inline int read() {
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int ans1 , ans2 , ans3 = inf , ans4 = inf , x[maxn] , y[maxn] , ans , n , opt;//ans1维护x-y的最大值，ans2维护x+y的最大值，ans3维护x-y的最小值，ans4维护x+y的最大值
signed main() {
    n = read();
    opt = read();
    for(int i = 1; i <= n; i++) x[i] = read() , y[i] = read() , ans1 = max(ans1 , x[i] - y[i]) , ans2 = max(ans2 , x[i] + y[i]) , ans3 = min(ans3 , x[i] - y[i]) , ans4 = min(ans4 , x[i] + y[i]);
    if(opt == 1) {//暴力枚举
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                int dx = x[i] - x[j] , dy = y[i] - y[j];
                ans = max(ans , dx * dx + dy * dy);
            }
        }
        cout << ans << endl;
    }else cout << max(ans1 - ans3 , ans2 - ans4) << endl;//数学公式
    return 0;
}