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

· · 题解

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

题目要求：

  1. 任意两点间欧几里得距离最大值的平方，对于两个点 (x_i, y_i) 和 (x_j, y_j)，欧几里得距离定义为 \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}。

  2. 任意两点间曼哈顿距离最大值，对于两个点 (x_i, y_i) 和 (x_j, y_j)，曼哈顿距离定义为 |x_i - x_j| + |y_i - y_j|。

因为只用输出距离最大值的平方，所以欧几里得距离只要输出 (x_i - x_j)^2 + (y_i - y_j)^2 。

Code

ll ans = 0;
upto(i, 1, n) {
    upto(j, 1, n) {
        num[i] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
        ans = max(ans, num[i]);
    }
}
cout << ans;

接下来考虑曼哈顿距离最大值。我一开始用的是暴力，结果 TLE 了。

upto(i, 1, n) {
    upto(j, 1, n) {
        num[i] = fabs(x[i] - x[j]) + fabs(y[i] - y[j]);
        ans = max(ans, num[i]);
    }
}
        cout << ans;

通过观察数据，我们发现 1\leq n \leq 10^6 ，因此 TLE 便是显而易见的。

正解

我们应当通过求极差的方式求出求平面曼哈顿最远点对。

极差是一个统计学中的概念，它表示一组数据中最大值与最小值之间的差异。用数学公式表示就是： 极差 = 最大值 - 最小值。

Code

ll maxa = LLONG_MIN, mina = LLONG_MAX;
ll maxb = LLONG_MIN, minb = LLONG_MAX;
    upto(i, 1, n) {
        maxa = max(maxa, x[i] + y[i]);
        mina = min(mina, x[i] + y[i]);
        maxb = max(maxb, x[i] - y[i]);
        minb = min(minb, x[i] - y[i]);
    }
cout << max(maxa - mina, maxb - minb);

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;// 1<=n<=1e6
#define maxn 10010
#define mod 1e9 + 7//998244353
#define upto(i, a, b) for (int i = a; i <= b; i++)//循环板子，拿走不谢
#define downto(i, a, b) for (int i = a; i >= b; i--)
#define rep(i, a, b) for (int i = a; i < b; i++)
typedef long long ll;//ll代替long long,节约录入时间
//using ll=long long;
//#define ll long long
template <typename T>//通用快读板子
inline void read(T &x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-')
            f = 0;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        x = x * 10 + ch - 48, ch = getchar();
    if (!f)
        x = -x;
}

ll maxa = LONG_LONG_MIN, mina = LONG_LONG_MAX;//||LLONG_MAX
ll maxb = LONG_LONG_MIN, minb = LONG_LONG_MAX;
ll n, opt, x[N], y[N], num[N];

int main() {
    ios::sync_with_stdio(false);//关流
    read(n);
    read(opt);
    upto(i, 1, n) {
        read(x[i]), read(y[i]);
    }
    upto(i, 1, n) {//循环求极差
        maxa = max(maxa, x[i] + y[i]);
        mina = min(mina, x[i] + y[i]);
        maxb = max(maxb, x[i] - y[i]);
        minb = min(minb, x[i] - y[i]);
    }
    if (opt == 1) {//求欧几里得距离最大值的平方
        ll ans = 0;
        upto(i, 1, n) {
            upto(j, 1, n) {
                num[i] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
                ans = max(ans, num[i]);
            }
        }
        cout << ans;
    } else if (opt == 2) {
        cout << max(maxa - mina, maxb - minb);
    }
    return 0;
}

鸣谢

严格来说，对于求曼哈顿距离最大值，本篇题解在一定程度上参考了 Miku_QwQ 求极差的思路，感谢TA。

我们下篇题解再会！