题解 P5098 【[USACO2004OPEN]Cave Cows 3 洞穴里的牛之三】

Heartlessly · 2019-06-19 07:50:17 · 题解

Description

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

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

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

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

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

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

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;
}