分数: 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