#T2350. 最近的营地 II(Nearest Campsites II)

最近的营地 II(Nearest Campsites II)

链接: https://cses.fi/problemset/task/3307

板块: Additional Problems I

时限: 1.00 s | 内存: 512 MB

题目描述

一个露营地表示为一个网格,其中每个方格可以包含一个营地,该营地要么已被预订,要么空闲。两个方格 (x1,y1)(x_1, y_1) 和 (x2,y2)(x_2, y_2) 之间的距离是曼哈顿距离 ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2|。

你的任务是找出从每个空闲营地到最近的已预订营地的距离。

输入

第一行包含两个整数 nn 和 mm:已预订和空闲营地的数量。

接下来的 nn 行描述已预订营地的位置。每行有两个整数 xx 和 yy。

接下来的 mm 行描述空闲营地的位置。每行有两个整数 xx 和 yy。

你可以假设每个方格至多包含一个营地。

输出

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

数据范围

1≤n,m≤1051 \le n, m \le 10^5 1≤x,y≤1061 \le x, y \le 10^6

样例输入

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

样例输出

2 5