← 返回题目列表

AtCoder · abc057_b

B. 检查点

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

有 N 学生和 M 检查点 xy- 平面。
的坐标 i第学生 (1 \leq i \leq N) is (a_i,b_i),以及编号为检查点的坐标 j (1 \leq j \leq M) is (c_j,d_j).
当老师发出信号时,每个学生必须前往距离最近的检查点 曼哈顿距离.
两点之间的曼哈顿距离 (x_1,y_1) 和 (x_2,y_2) is |x_1-x_2|+|y_1-y_2|.
在这里, |x| 表示绝对值 x.
如果学生有多个最近的检查点,他/她将选择索引最小的检查点。
每个学生将前往哪个检查站?

约束

  • 1 \leq N,M \leq 50
  • -10^8 \leq a_i,b_i,c_j,d_j \leq 10^8
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
a_1 b_1
:  
a_N b_N
c_1 d_1
:  
c_M d_M

输出

打印 N 行。
的 i第行 (1 \leq i \leq N) 应包含检查点的索引 i第一个学生走了。


样本输入 1

2 2
2 0
0 0
-1 0
1 0

示例输出 1

2
1

第一个学生和每个检查点之间的曼哈顿距离是:

  • 对于检查点 1: |2-(-1)|+|0-0|=3
  • 对于检查点 2: |2-1|+|0-0|=1

最近的检查点是检查点 2。因此,输出中的第一行应包含 2.

第二个学生与每个检查点之间的曼哈顿距离为:

  • 对于检查点 1: |0-(-1)|+|0-0|=1
  • 对于检查点 2: |0-1|+|0-0|=1

当有多个最近的检查点时,学生将前往索引最小的检查点。因此,输出中的第二行应包含 1.


示例输入 2

3 4
10 10
-10 -10
3 3
1 2
2 3
3 5
3 5

示例输出 2

3
1
2

同一坐标处可以有多个检查点。


示例输入 3

5 5
-100000000 -100000000
-100000000 100000000
100000000 -100000000
100000000 100000000
0 0
0 0
100000000 100000000
100000000 -100000000
-100000000 100000000
-100000000 -100000000

示例输出 3

5
4
3
2
1