← 返回题目列表

Codeforces · 698/D

D. 利马克和射击点

中文机器翻译题面 查看原题

熊地是一个危险的地方。利马克无法步行旅行。相反,他有k块魔法传送石。每块石头最多可以使用一次。第 i 块石头可以传送到一个点(axi、ayi)。 Limak 可以按任意顺序使用石头。

Bearland中有n只怪物。其中第 i 个位于 (mxi, myi)。

给定的 k + n 点是两两不同的。

每次传送后,利马克可以向某个方向射箭。箭头将击中所选方向上的第一个怪物。然后,一支箭和一只怪物都消失了。长时间呆在一个地方是很危险的,所以利马克只能从一个地方射出一支箭。

如果利马克可能会击中怪物,则该怪物应该感到害怕。有多少怪物应该害怕利马克?

输入

输入的第一行包含两个整数 k 和 n (1 ≤ k ≤ 7, 1 ≤ n ≤ 1000) – 石头的数量和怪物的数量。

以下 k 行的第 i 行包含两个整数 axi 和 ayi (- 109 ≤ axi, ayi ≤ 109) - Limak 可以使用第 i 块石头传送到的坐标。

最后 n 行的第 i 行包含两个整数 mxi 和 myi (- 109 ≤ mxi, myi ≤ 109) — 第 i 个怪物的坐标。

给定的 k + n 点是两两不同的。

输出

打印应该害怕 Limak 的怪物数量。

示例

输入 #1

2 4
-2 -1
4 5
4 2
2 1
4 -1
1 -1

输出 #1

3

输入 #2

3 8
10 20
0 0
20 40
300 600
30 60
170 340
50 100
28 56
90 180
-4 -8
-1 -2

输出 #2

5

注意

在第一个样本中,有两个石头和四个怪物。石头可以传送到点 (- 2, - 1) 和 (4, 5),在下图中标记为蓝色。怪物位于 (4, 2)、(2, 1)、(4, - 1) 和 (1, - 1) 处,标记为红色。 (4, - 1) 的怪物不应该害怕,因为利马克不可能用箭射中它。其他三个怪物可以被击中,因此答案是3。

在第二个样本中,应该害怕五个怪物。安全怪物是那些位于 (300, 600)、(170, 340) 和 (90, 180) 的怪物。