本文最后更新于34 天前，其中的信息可能已经过时，如有错误请发送邮件到big_fw@foxmail.com

K. 点直径

每次测试时间限制：3 秒
内存限制：256 MB

题目描述

佐罗又在某个平坦的小岛上迷路了，岛上有 $n$ 个地标。山治气坏了，想用地图给他指路。第 $i$ 个地标的坐标为 $(x_i, y_i)$。

为了照顾佐罗糟糕的方向感，山治决定从地图上最多擦除两个地标。地图的“迷失直径”定义为剩余地标中任意两点之间的最大曼哈顿距离。

两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离为 $|x_1 – x_2| + |y_1 – y_2|$。如果剩余地标少于两个，则直径为 $0$。

求山治在最多擦除两个地标后，能达到的最小可能直径。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例数。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）—— 点的数量。

接下来 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$-10^9 \le x_i, y_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 最小的可能直径。

示例

输入

输出

0
2

示例说明

第一个测试用例中，擦除 $(10,0)$ 和 $(0,10)$，只剩一个点，直径为 $0$。
第二个测试用例中，擦除两个对角点后，剩余两个点之间的曼哈顿距离为 $2$。

解题思路

这道题我学到最大的地方就是：对于任意两点 $P_i(x_i, y_i)$ 和 $P_j(x_j, y_j)$，可以用恒等式转化为

$$
|x_i – x_j| + |y_i – y_j| = \max\left{ |(x_i + y_i) – (x_j + y_j)|,\ |(x_i – y_i) – (x_j – y_j)| \right}
$$

（取绝对值后取最大，实际等价于两个维度差值的最大值）。

令 $u_i = x_i + y_i$，$v_i = x_i – y_i$，那么一组点的最大曼哈顿距离就是

$$
D = \max\left( \max_i u_i – \min_i u_i,\ \max_i v_i – \min_i v_i \right)
$$

因此删除点后只需要重新计算剩余点中 $u$ 和 $v$ 的极差。

若删除 $k$ 个点（$k \le 2$），我们只需要计算剩余点上上述两个差值的最大值。为了最小化直径，我们要尽量删除极端点——即贡献最大值和最小值的点。
真正可能影响最终答案的点有：

$x+y$ 最大的前 $2$ 个点
$x+y$ 最小的前 $2$ 个点
$x-y$ 最大的前 $2$ 个点
$x-y$ 最小的前 $2$ 个点

将这些点去重后，候选点不超过 $8$ 个，然后枚举删除其中 $2$ 个点的直径，取最小值即可。
当 $n \le 3$ 时，答案就是 $0$，加个特判。

参考代码

//Sunshine sunshine ladybugs awake,
//Clap your hooves and do a little shack.
#include<bits/stdc++.h>

#define int long long
#define endl "\n"

using namespace std;

using PII = pair<int,int>;
const int MAXN = 300005;
const int mod = 998244353;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n; cin >> n;
    vector<PII> point(n);
    vector<PII> sum, diff;

    for(int i = 0; i < n; i++){
        auto &[x, y] = point[i];
        cin >> x >> y;
        sum.push_back({x + y, i});
        diff.push_back({x - y, i});
    }

    sort(sum.begin(), sum.end());
    sort(diff.begin(), diff.end());

    set<int> candidate;
    int take = min(2ll, n);

    for(int i = 0; i < take; i++){
        candidate.insert(sum[i].second);
        candidate.insert(sum[n - 1 - i].second);
        candidate.insert(diff[i].second);
        candidate.insert(diff[n - 1 - i].second);
    }

    vector<int> candidates(candidate.begin(), candidate.end());

    auto calculate = [&](int ban1, int ban2) -> int {
        int minU = INF, maxU = -INF;
        int minV = INF, maxV = -INF;
        int count = 0;

        for(int i = 0; i < n; i++){
            if(i == ban1 || i == ban2) continue;
            count++;
            auto [x, y] = point[i];
            int u = x + y;
            int v = x - y;
            minU = min(minU, u);
            maxU = max(maxU, u);
            minV = min(minV, v);
            maxV = max(maxV, v);
        }

        if(count < 2) return 0;
        return max(maxU - minU, maxV - minV);
    };

    if (n <= 3) {
        cout << 0 << endl;
        return;
    }

    int answer = INF;
    int m = candidates.size();

    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            answer = min(answer, calculate(candidates[i], candidates[j]));
        }
    }

    cout << answer << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}