题解：AT_abc215_f [ABC215F] Dist Max 2

· · 题解

NOIP2025 加油！

题目传送门 AT

题目大意

有 n 个点 (x_i, y_i)，求所有不同的两个点的“距离”的最大值。

“距离”定义：对于两个点 i, j，这两个点的距离为 \min(|x_i - x_j|, |y_i - y_j|)。

n \le 2 \times 10^5

。

题目分析

看到最小值最大，先想二分答案。

考虑当前二分到 mid，满足的要求为 \min(|x_i - x_j|, |y_i - y_j|) \ge mid，即 |x_i - x_j| \ge mid 且 |y_i - y_j| \ge mid。

因为有两个东西需要处理，非常不好弄。那么我们就先定住一个。我们不妨把 x 定住。

按 x 从小到大排序，用双指针找出满足 x_r - x_l \ge mid，那么 |x_i - x_j| \ge mid 就满足了，其中 i \le l, r \le j。

接下来处理 y。我们求出 l 前面和 r 后面的最值，判断前缀最大值减去后缀最小值或者后缀最大值减去前缀最小值大于等于 mid 即可。

时间复杂度 \mathcal{O}(n \log V)，其中 V 为 x, y 的值域。

code

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
    ll res = 0, f = 1; char ch = gc();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
    while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
    return res * f;
}
inline void write(ll x)
{
    if (x < 0) x = -x, pc('-');
    if (x > 9) write(x / 10);
    pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 2e5 + 5;
int lmin[N], lmax[N], rmin[N], rmax[N]; // 前缀 / 后缀 最小值 / 最大值
struct node {
    int x, y;
} a[N];
bool cmp(node x, node y) { return x.x < y.x; }
int n;
bool check(int mid)
{
    for (int i = 1, j = 1; i <= n; i++)
    {
        while (j < n && a[j].x - a[i].x < mid) j++;
        // 满足 |x_i - x_j| >= mid
        if (a[j].x - a[i].x < mid) break;
        if (lmax[i] - rmin[j] >= mid || rmax[j] - lmin[i] >= mid) return true; 
    }
    return false;
}
int main()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i].x = read(), a[i].y = read();
    sort(a + 1, a + n + 1, cmp);
    lmin[0] = INF;
    for (int i = 1; i <= n; i++) lmin[i] = min(lmin[i - 1], a[i].y), lmax[i] = max(lmax[i - 1], a[i].y);
    rmin[n + 1] = INF;
    for (int i = n; i >= 1; i--) rmin[i] = min(rmin[i + 1], a[i].y), rmax[i] = max(rmax[i + 1], a[i].y);
    int l = 0, r = 1e9, ans = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    write(ans);
    return 0;
}

// NOIP2025 rp++