题目描述

难度分:$1853$

输入$n(2 \leq n \leq 2 \times 10^5)$和$n$个二维坐标点，范围$[0,10^9]$。保证所有点互不相同。

定义两点$(x_i,y_i)$和$(x_j,y_j)$的距离为$min(|x_i-x_j|,|y_i-y_j|)$。

输出两点之间的最大距离。

输入样例$1$

3
0 3
3 1
4 10

输出样例$1$

4

输入样例$2$

4
0 1
0 4
0 10
0 6

输出样例$2$

0

输入样例$3$

8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

输出样例$3$

801

算法

二分答案

这个二分稍微隐藏了一下，分析了一下发现有单调性才注意到本质是最大化最小值。距离是用最小值定义的，而我们要最大化这个最小值，就可以用二分。

直觉上要先将所有坐标点按照$x$排序，然后遍历所有点，对每个点$(x_i,y_i)$找到离它最远的点的距离，维护距离的最大值。对于一个给定的坐标点$(x_i,y_i)$，要想确定离它最远的那个点的距离比较困难。但是给定一个距离$dist$，确定有没有一个点距离它$\geq dist$是比较简单的，$x$已经有序了，因此可以在$x_i$的$dist$距离之外看看有没有$y$坐标$\geq dist$的点，有就说明存在一个点距离$(x_i,y_i)$是$\geq dist$的。

这样就可以二分这个距离的最大值了，因为如果存在一个点对，距离$\geq dist$，对于更小的$dist$肯定也存在符合条件的点对，存在单调性。对于一个给定的$dist$，检查是否存在一个点对，使得点对间的距离$\geq dist$，分为以下两种情况：

1. 存在就记录答案并往右搜索看点对距离能不能更大。
2. 不存在就往左搜索。

最后我们考虑对于一个点$(x_i,y_i)$如何确定是否存在一个点$(x_j,y_j)$使得$min(|x_i-x_j|,|y_i-y_j|) \geq dist$。此时$x$是有序的，比较容易确定$|x_i-x_j| \geq dist$的$j$处于前缀和后缀上，那么只需要知道这段前缀或者后缀上最大的那个$y$值是否满足$y-y_i \geq dist$即可。因此，对于排序后的所有点对$(x_i,y_i)$，需要预处理出一个前缀最大值数组$premax$和一个后缀最大值数组$sufmax$，这样就可以做了。

复杂度分析

时间复杂度

对所有点对排序的时间复杂度为$O(nlog_2n)$；预处理出前后缀最大值数组$premax$和$sufmax$的时间复杂度为$O(n)$；二分的值域是$U$，因此外层二分的时间复杂度是$O(log_2U)$，而每个$dist$的$check$需要遍历$i \in [1,n]$，时间复杂度为$O(n)$，每个点$(x_i,y_i)$要找到前缀$[1,L]$和后缀$[R,n]$，使得这一段区间里面点的横坐标离$x$的距离$\geq dist$，由于$x$已经按照升序排列好了，这两个区间可以在$O(log_2n)$的时间复杂度下二分确定，所以$check$的时间复杂度为$O(nlog_2n)$，二分答案的时间复杂度为$O(nlog_2nlog_2U)$。

综上，整个算法的时间复杂度为$O(nlog_2n+nlog_2nlog_2U)$。

空间复杂度

除了输入所有点所占空间，空间消耗的瓶颈在于前后缀的最大值数组$premax$和$sufmax$，它们都是线性的。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, premax[N], sufmax[N];

struct Point {
    int x, y;
    bool operator<(const Point other) {
        return x < other.x;
    }
} points[N];

bool check(int dist) {
    for(int i = 1; i <= n; i++) {
        int l = 1, r = i - 1, L = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(points[mid].x + dist <= points[i].x) {
                L = mid;
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        if(L >= 1 && premax[L] >= points[i].y + dist) {
            return true;
        }
        l = i + 1, r = n;
        int R = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(points[mid].x - dist >= points[i].x) {
                R = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        if(R >= 1 && sufmax[R] >= points[i].y + dist) {
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &points[i].x, &points[i].y);
    }
    sort(points + 1, points + n + 1);
    premax[1] = points[1].y;
    for(int i = 2; i <= n; i++) {
        premax[i] = max(premax[i - 1], points[i].y);
    }
    sufmax[n] = points[n].y;
    for(int i = n - 1; i >= 1; i--) {
        sufmax[i] = max(sufmax[i + 1], points[i].y);
    }
    int l = 0, r = 1e9;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(check(mid)) {
            l = mid;
        }else {
            r = mid - 1;
        }
    }
    printf("%d\n", r);
    return 0;
}