题解 P5098 【[USACO2004OPEN]Cave Cows 3 洞穴里的牛之三】
Heartlessly
2019-06-19 07:50:17
## Description
给定 $n$ 个点，每个点的坐标为 $(x,y)$，求曼哈顿距离的最大点对，输出这个最大值。
$(1 \leq n \leq 5 \times 10^4,-10^6 \leq x,y \leq 10^6)$
## 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$ 的值有关，所以最后的答案为
$$
\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
```cpp
#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
```cpp
#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;
}
```