题目详情题解（0）讨论（0）提交记录（0）

CF698D.Limak and Shooting Points

省选/NOI-

通过率：0%

时间限制：3.00s

内存限制：256MB

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Bearland is a dangerous place. Limak can’t travel on foot. Instead, he has k magic teleportation stones. Each stone can be used at most once. The i-th stone allows to teleport to a point (ax__i, ay__i). Limak can use stones in any order.

There are n monsters in Bearland. The i-th of them stands at (mx__i, my__i).

The given k + n points are pairwise distinct.

After each teleportation, Limak can shoot an arrow in some direction. An arrow will hit the first monster in the chosen direction. Then, both an arrow and a monster disappear. It’s dangerous to stay in one place for long, so Limak can shoot only one arrow from one place.

A monster should be afraid if it’s possible that Limak will hit it. How many monsters should be afraid of Limak?

Bearland 是一个危险的地方。Limak 无法步行旅行，他拥有 kk 颗魔法传送石。每颗石头最多只能使用一次。第 ii 颗石头可将 Limak 传送到点 (axi, ayi)(ax_i,\, ay_i)。Limak 可以按任意顺序使用这些石头。

Bearland 中有 nn 只怪物，其中第 ii 只怪物位于点 (mxi, myi)(mx_i,\, my_i)。

给定的 k+nk + n 个点两两互不相同。

每次传送后，Limak 可朝某个方向射出一支箭。该箭会击中该方向上第一个遇到的怪物；随后，这支箭和该怪物均消失。由于长时间停留在同一地点十分危险，Limak 在每个位置最多只能射出一支箭。

若存在某种策略使得 Limak 可能击中某只怪物，则该怪物应感到畏惧。问：共有多少只怪物应畏惧 Limak？

输入格式

The first line of the input contains two integers k and n (1 ≤ k ≤ 7, 1 ≤ n ≤ 1000) — the number of stones and the number of monsters.

The i-th of following k lines contains two integers ax__i and ay__i ( - 109 ≤ ax__i, ay__i ≤ 109) — coordinates to which Limak can teleport using the i-th stone.

The i-th of last n lines contains two integers mx__i and my__i ( - 109 ≤ mx__i, my__i ≤ 109) — coordinates of the i-th monster.

The given k + n points are pairwise distinct.

输入的第一行包含两个整数 kk 和 nn（1≤k≤71 \leq k \leq 7，1≤n≤10001 \leq n \leq 1000）——分别表示石头的数量和怪物的数量。

接下来的 kk 行中，第 ii 行包含两个整数 axiax_i 和 ayiay_i（−109≤axi,ayi≤109-10^9 \leq ax_i, ay_i \leq 10^9）——表示 Limak 使用第 ii 块石头可传送至的坐标。

最后的 nn 行中，第 ii 行包含两个整数 mximx_i 和 myimy_i（−109≤mxi,myi≤109-10^9 \leq mx_i, my_i \leq 10^9）——表示第 ii 个怪物的坐标。

给定的 k+nk + n 个点两两互不相同。

输出格式

Print the number of monsters which should be afraid of Limak.

输出应该害怕 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

说明/提示

In the first sample, there are two stones and four monsters. Stones allow to teleport to points ( - 2,  - 1) and (4, 5), marked blue in the drawing below. Monsters are at (4, 2), (2, 1), (4,  - 1) and (1,  - 1), marked red. A monster at (4,  - 1) shouldn't be afraid because it's impossible that Limak will hit it with an arrow. Other three monsters can be hit and thus the answer is 3.

In the second sample, five monsters should be afraid. Safe monsters are those at (300, 600), (170, 340) and (90, 180).

在第一个样例中，有两块石头和四只怪物。石头允许传送到点 (−2,−1)(-2, -1) 和 (4,5)(4, 5)，如下图中蓝色标记所示。怪物位于 (4,2)(4, 2)、(2,1)(2, 1)、(4,−1)(4, -1) 和 (1,−1)(1, -1)，以红色标记。位于 (4,−1)(4, -1) 的怪物无需害怕，因为 Limak 不可能用箭射中它。其余三只怪物均可能被射中，因此答案为 33。

在第二个样例中，五只怪物需要感到害怕。安全的怪物位于 (300,600)(300, 600)、(170,340)(170, 340) 和 (90,180)(90, 180)。

输入解题思路，AI测评打分。不知道怎么写?

首页