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

· · 题解

题目传送门

一道水题

证明：

对于两个点 (x_i,y_i) 和 (x_j,y_j)，其曼哈顿距离有：

  1. (x_i + y_i) - (x_j + y_j)
  2. (x_i + y_i) - (x_j - y_j)
  3. -(x_i + y_i) + (x_j + y_j)
  4. -(x_i + y_i) + (x_j - y_j)

所以可以枚举所有的 (x_i + y_i) 和 (x_i - y_i)，分别求其 \max 和 \min，差的较大值即为曼哈顿距离最大值。

Code

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const long long maxn = 1e6 + 5;
long long n, op, ans, x[maxn], y[maxn];
// 十年 OI 一场空，不开 long long 见祖宗
signed main() {
    cin >> n >> op;
    for (long long i = 1; i <= n; i++) cin >> x[i] >> y[i];
    if (op == 1) {
        for (long long i = 1; i <= n; i++) 
            for (long long j = i + 1; j <= n; j++) 
                ans = max(ans, (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
    } else {
        long long mx1 = 0, mx2 = 0, mn1 = inf, mn2 = inf;
        for (long long i = 1; i <= n; i++) {
            mx1 = max(mx1, x[i] - y[i]);
            mx2 = max(mx2, x[i] + y[i]);
            mn1 = min(mn1, x[i] - y[i]);
            mn2 = min(mn2, x[i] + y[i]);
        } // 计算每个点 i 的 xi 和 yi 的和与差的最大值和最小值
        ans = max(mx1 - mn1 , mx2 - mn2);
    }
    cout << ans << endl;
    return 0;
}

其实很简单的，就是需要懂一些技巧。