在潘多拉星球的草原上,纳美族正在举行一场隆重的仪式——重铠马的选择仪式。
每匹重铠马都会站在固定的位置挑选自己的主人,主人也必须站在固定的位置等待重铠马的选择。
现场共有 N 位候选人(编号 1 \sim N),每位候选人的位置为 (PX_i, PY_i),同时有 M 匹重铠马(编号 1 \sim M),它们的初始位置为 (HX_j, HY_j)。
每匹重铠马按照编号 1 \sim M 的顺序,依次选择与自己距离最近,且没有被其他重铠马选中的候选人作为自己主人。如果有多位候选人与某匹重铠马的距离相同,则重铠马会优先选择编号较小的候选人。
然而,由于重铠马数量有限,一些候选人可能无法被任何重铠马选中。
你的任务是编程找出所有未被重铠马选中的候选人编号,并按编号从小到大的顺序输出。
第一行包含两个整数 N 和 M,分别表示候选人的数量和重铠马的数量。
接下来的 N 行,每行包含两个整数 PX_i 和 PY_i,表示第 i 位候选人的位置。
再接下来的 M 行,每行包含两个整数 HX_j 和 HY_j,表示第 j 匹重铠马的初始位置。
输出若干行,每行一个整数,按照从小到大的顺序,依次输出未被重铠马选中的候选人编号。
如果所有候选人都被选中,则输出 0。
3 2 1 0 3 1 2 1 1 1 1 2
2
9 5 -1 2 6 -2 3 0 6 8 -5 3 8 -2 -6 7 3 -3 3 -5 -2 9 -10 -1 -7 1 1 2 8 6
2 6 8 9
18 6 1 7 1 4 -10 10 12 0 8 -2 -2 6 1 10 6 1 7 3 8 9 10 10 -6 4 1 10 -3 4 3 -2 -10 0 9 -3 9 -1 -7 5 10 2 4 7 8 -1 -8 -8 8 -8
2 3 6 7 8 9 10 11 13 14 15 18
有 3 个人,2 匹马。
1 号马到编号为 1 和编号为 3 的人都是最近的,按照规则,它将选择 1 号做主人。
2 号马选择离它最近的 3 号做主人。
因此编号为 2 的人未被任何重铠马选中。
在解决问题时,需要计算重铠马与候选人之间的距离,假设求第 j 匹重铠马和第 i 个人之间的距离,则求解公式为:d(j, i) = \sqrt{(HX_j - PX_i)^2 + (HY_j - PY_i)^2}。
测试点 1 满足 M=N。
测试点 2 满足 M=1, N=5。
测试点 3 \sim 4 满足 1 \le M \le N \le 20。
测试点 6 \sim 10 满足 1 \le M \le N \le 1000,-10^6 \leq PX_i, PY_i, HX_j, HY_j \leq 10^6。