← 返回题目列表

AtCoder · abc442_e

H. 激光高桥

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

分数: 450 点

问题陈述

有 N 二维平面上的怪物。 怪物编号为 1 to N,以及怪物的坐标 i 是 (X_i,Y_i)。 在这里, (X_i,Y_i) \neq (0,0)。 (每个怪物都可以视为一个静止点。即怪物没有大小。)

高桥正站在这个位面的原点。 强大的激光总是从他的眼睛中发射出来,瞬间摧毁他所面对方向的怪物。 如果他所面对的方向存在多个怪物,那么所有怪物都会立即被消灭。

青木正在指挥 Q 独立 思想实验。 的 j第思想实验如下:

  • 最初,高桥面朝怪物的方向 A_j。从现在开始,高桥将轮流 顺时针 并在他面对怪物的方向时停止 B_j。 这里,一共有多少个怪物(包括怪物) A_j 和 B_j) 会被摧毁吗?如果怪物 A_j 和 B_j 存在于与原点相同的方向,高桥根本不旋转。

找到每个思想实验的答案。

约束

  • 2\leq N \leq 2\times 10^5
  • 1\leq Q \leq 2\times 10^5
  • -10^9\leq X_i,Y_i \leq 10^9
  • (X_i,Y_i)\neq (0,0)
  • 1\leq A_j,B_j\leq N
  • A_j\neq B_j
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N Q
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
A_1 B_1
A_2 B_2
\vdots
A_Q B_Q

输出

输出 Q 行。 的 j第行 (1\leq j \leq Q) 应包含以下问题的答案 j第思想实验。


示例输入 1

5 4
0 1
1 -2
1 0
-2 0
3 0
4 1
1 4
5 4
3 5

示例输出 1

2
5
4
2

  • 1-st思想实验:最初,高桥面朝怪物的方向 4 (此时,怪物 4 已被摧毁)。 从这里开始,他继续顺时针旋转,在面对怪物的方向时停止。 1 (此时,怪物 1 已被摧毁)。 由于他没有面向任何其他怪物,所以答案是 2.
  • 2-nd思想实验:最初,高桥面朝怪物的方向 1 (此时,怪物 1 已被摧毁)。 从这里开始,当他继续顺时针旋转时,他面向怪物的方向 3 和 5 一路走来,所以他们被摧毁了。 当他继续旋转时,他面向怪物的方向 2 一路走来,就这样被毁掉了。 终于,在面向怪物的方向时,他停了下来。 4 (此时,怪物 4 已被摧毁)。 因此,答案是 5.
  • 3-rd思想实验:怪物 3, 5, 2, 4 被摧毁,所以答案是 4.
  • 4第思想实验:怪物 3, 5 被摧毁,所以答案是 2。 请注意,自从怪物 3 和 5 存在于与原点相同的方向,高桥根本不旋转。

示例输入 2

2 1
1 2
1 2
1 2

示例输出 2

2

同一坐标处可能存在多个怪物。


示例输入 3

8 10
-84 -60
-100 8
77 55
-14 -10
50 -4
-63 -45
26 -17
-7 -5
3 7
2 4
8 4
8 4
7 1
1 7
6 3
4 7
4 5
2 6

示例输出 3

3
8
4
4
5
8
6
8
7
8