2848 - 重铠马的选择

题目描述

在潘多拉星球的草原上,纳美族正在举行一场隆重的仪式——重铠马的选择仪式。

每匹重铠马都会站在固定的位置挑选自己的主人,主人也必须站在固定的位置等待重铠马的选择。

现场共有 N 位候选人(编号 1 \sim N),每位候选人的位置为 (PX_i, PY_i),同时有 M 匹重铠马(编号 1 \sim M),它们的初始位置为 (HX_j, HY_j)

每匹重铠马按照编号 1 \sim M 的顺序,依次选择与自己距离最近,且没有被其他重铠马选中的候选人作为自己主人。如果有多位候选人与某匹重铠马的距离相同,则重铠马会优先选择编号较小的候选人。

然而,由于重铠马数量有限,一些候选人可能无法被任何重铠马选中。

你的任务是编程找出所有未被重铠马选中的候选人编号,并按编号从小到大的顺序输出。

输入

第一行包含两个整数 NM,分别表示候选人的数量和重铠马的数量。

接下来的 N 行,每行包含两个整数 PX_iPY_i,表示第 i 位候选人的位置。

再接下来的 M 行,每行包含两个整数 HX_jHY_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
说明

样例 1 说明

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

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题