Nearest Campsites I

题目描述

一个露营地表示为一个网格，每个格子可能包含一个被预订的或空闲的营位。两个格子 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的距离是曼哈顿距离 $|x_1 - x_2| + |y_1 - y_2|$。 你的任务是找到从一个空闲营位到最近被预订营位的最大距离。

输入格式

第一行有两个整数 n 和 m：被预订营位和空闲营位的数量。 接下来的 n 行描述被预订营位的位置。每行有两个整数 $x$ 和 $y$。 接下来的 m 行描述空闲营位的位置。每行有两个整数 $x$ 和 $y$。 你可以假设每个格子最多包含一个营位。

输出格式

输出一个整数：到最近被预订营位的最长距离。

4 2
1 1
5 2
2 6
4 7
1 3
7 5

5

提示

$1 \le n, m \le 10^5$ $1 \le x, y \le 10^6$ 说明：下图显示了露营地的地图： 在这种情况下，最佳选择是右边的空闲营位，它到最近被预订营位的距离为 5。

标签: CSES3306|附加题1

来源

CSES3306|附加题1