Nearest Campsites II

题目描述

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

输入格式

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

输出格式

输出 m 个整数：按输入顺序给出每个空闲营地到最近已预订营地的距离。

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

2 5

提示

$1 \le n, m \le 10^5$ $1 \le x, y \le 10^6$ 样例解释：下图显示了营地图： 第一个空闲营地（左边）到最近已预订营地的距离是 2，第二个空闲营地（右边）到最近已预订营地的距离是 5。

标签: CSES3307|附加题1

来源

CSES3307|附加题1