「Luogu P5098」「USACO04OPEN」Cave Cows 3 洞穴里的牛之三

Description

给定 $n$ 个点，每个点的坐标为 $(x,y)$，求曼哈顿距离的最大点对，输出这个最大值。

$(1 \leq n \leq 5 \times 10^4,-10^6 \leq x,y \leq 10^6)$

Source

Solution 1

根据题意，对于式子 $\left | x_1-x_2\right| +\left | y_1-y_2\right| $，我们可以分成四种情况考虑：

第一种情况：$x_1 - x_2 \geq 0,y_1 - y_2 \geq 0$

$\begin{aligned} &\left | x_1 - x_2 \right | + \left | y_1 - y_2\right |\\ =\ & x_1 - x_2 + y_1 - y_2\\ =\ & (x_1 + y_1) - (x_2 + y_2)\\ \end{aligned}$

第二种情况：$x_1 - x_2 < 0,y_1 - y_2 \geq 0$

$\begin{aligned} &\left | x_1 - x_2 \right | + \left | y_1 - y_2\right |\\ =\ & x_2 - x_1 + y_1 - y_2\\ =\ & (x_2 - y_2) - (x_1 - y_1)\\ \end{aligned}$

第三种情况：$x_1 - x_2 \geq 0,y_1 - y_2 < 0$

$\begin{aligned} &\left | x_1 - x_2 \right | + \left | y_1 - y_2\right |\\ =\ & x_1 - x_2 + y_2 - y_1\\ =\ & (x_1 - y_1) - (x_2 - y_2)\\ \end{aligned}$

第四种情况：$x_1 - x_2 < 0,y_1 - y_2 < 0$

$\begin{aligned} &\left | x_1 - x_2 \right | + \left | y_1 - y_2\right |\\ =\ & x_2 - x_1 + y_2 - y_1 \\ =\ & (x_2 + y_2) -(x_1 + y_1)\\ \end{aligned}$

每种情况的答案要么只与 $x+y$ 的值有关，要么只与 $x-y$ 的值有关，所以最后的答案为

$\max \begin{Bmatrix} \max \begin{Bmatrix} x_i + y_i \end{Bmatrix} - \min \begin{Bmatrix} x_i + y_i \end{Bmatrix},\max \begin{Bmatrix} x_i - y_i \end{Bmatrix} - \min \begin{Bmatrix} x_i - y_i \end{Bmatrix} \end{Bmatrix}$

Code 1

#include <bits/stdc++.h>
using namespace std;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int n, x, y, minx = 0x7fffffff, maxx, miny = 0x7fffffff, maxy;

int main() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(x), read(y);
        minx = min(minx, x + y), maxx = max(maxx, x + y);
        miny = min(miny, x - y), maxy = max(maxy, x - y);
    }
    write(max(maxx - minx, maxy - miny));
    putchar('\n');
    return 0;
}

Solution 2

我们考虑将题目所求的 曼哈顿距离 转化为 切比雪夫距离，即把每个点的坐标 $(x,y)$ 变为 $(x + y, x - y)$ 。

所求的答案就变为 $\max \begin{Bmatrix} \max\begin{Bmatrix} \left | x_i - x_j\right| ,\left | y_i - y_j\right| \end{Bmatrix} \end{Bmatrix}$ 。

在所有点中，横坐标之差的最大值和纵坐标之差的最大值都有可能成为答案，所以我们只需要预处理出 $x,y$ 的最大值和最小值即可。时间复杂度为 $O(n)$ 。

Code 2

#include <bits/stdc++.h>
using namespace std;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int n, x, y, a, b, minx = 0x7fffffff, maxx, miny = 0x7fffffff, maxy;

int main() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a), read(b);
        x = a + b, y = a - b;
        minx = min(minx, x), maxx = max(maxx, x);
        miny = min(miny, y), maxy = max(maxy, y);
    }
    write(max(maxx - minx, maxy - miny));
    putchar('\n');
    return 0;
}