「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

[Luogu]P5098

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}

本文标题:「Luogu P5098」「USACO04OPEN」Cave Cows 3 洞穴里的牛之三

文章作者:Heartlessly

发布时间:2019年06月19日 - 07:34:21

最后更新:2019年06月19日 - 07:41:44

原始链接:https://heartlessly.github.io/problems/luogu-p5098/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%