Checkpoints

题目描述

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

输入格式

输入由标准输入按以下格式提供： $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$ 名学生前往的检查点的编号。

2 2
2 0
0 0
-1 0
1 0

2
1

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

3
1
2

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

5
4
3
2
1

提示

$1 \leq N,M \leq 50$ $-10^8 \leq a_i,b_i,c_j,d_j \leq 10^8$ 所有输入值均为整数。第一名学生到各检查点的曼哈顿距离为：

到检查点 $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$.
检查点可能存在相同的坐标。

标签: AtCoder|abc057B

来源

AtCoder|abc057B