P2994 [USACO10OCT] Dinner Time S

题目描述

给出 $N$ 头奶牛的坐标 $(CX_i , CY_i)$，编号为 $1 \dots N$；

给出 $M$ 个座位的坐标 $(SX_j , SY_j)$，编号为 $1 \dots M$。

然后开始牛抢座位坐。

• 所有牛同时出发，走直线距离，速度一样。
• 若两头牛同时到达同一个座位，编号小的牛有更多优先权。

假设所有牛都演练过多次抢座位，各自按最优策略抢座位，求无法抢到座位的奶牛编号。

注：在计算中可能会有超过 $32$ 位整数范围但在 $64$ 位整数范围内的数。

输入格式

第一行整数 $N \ M (1 \le N \le 10^3 ,1 \le M \le N )$。

下来 $N$ 行，每行整数 $CX_i$ 和 $CY_i$。

下来 $M$ 行，每行整数 $SX_j$ 和 $SY_j$。

（$-10^6 \le CX_i , CY_i , SX_j , SY_j \le 10^6$）

输出格式

输出 $(N-M)$ 行，每行一个无法抢到座位的奶牛编号。奶牛的编号应递增排序。

输入输出样例 #1

输入 #1

2 1 
0 1 
1 0 
1 10

输出 #1

2