分数: 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