← 返回题目列表

Codeforces · 1599/D

D. 气泡破裂

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

坐标平面中有 $$$N$$$ 个气泡。气泡非常小,可以假设每个气泡都是一个点 $$$(X_i, Y_i)$$$。

$$$Q$$$ 泡泡杯决赛入围者计划与泡泡一起玩。每位决赛选手都会链接使用无限长的泡泡杯棒来弹出一些泡泡。第 $$$i$$$ 决赛入围者希望将棍子放在矢量 $$$(dxi, dyi)$$$ 的方向上,并玩以下游戏,直到 $$$K_i$$$ 气泡被弹出。游戏开始时,决赛选手将棍子放在矢量 $$$(dx_i, dy_i)$$$ 的方向上,并将其从无穷远向左扫过,直到碰到某个气泡,气泡立即弹出。保证这一步只会击中一个气泡。之后,决赛选手开始以逆时针方向旋转棒,旋转中心位于上一个气泡被弹出的位置。当下一个气泡被击中时,它立即破裂并成为新的旋转中心。该过程持续进行,直到 $$$K_i$$$ 气泡被弹出。保证这个过程中木棍不会同时击中两个气泡。

对于每个决赛入围者,找出最后会弹出的气泡。请注意,每个游戏都以所有 $$$N$$$ 气泡的配置开始,因此游戏不依赖于之前的游戏。

输入

第一行包含一个整数 $$$N$$$ — 气泡的数量。 ($$$1 \leq N \leq 10^5$$$)

接下来的 $$$N$$$ 行包含两个整数。第 $$$i$$$ 行包含整数 $$$X_i$$$ 和 $$$Y_i$$$ — 第 $$$i$$$ 气泡的坐标。 ($$$-10^9 \leq X_i, Y_i \leq 10^9$$$, $$$(X_i, Y_i) \neq (X_j, Y_j)$$$ 对于 $$$i \neq j$$$)

下一行包含一个整数 $$$Q$$$ — 愿意玩泡泡的决赛入围者的数量。 ($$$1 \leq Q \leq 10^5$$$)

接下来的 Q 行每行包含 3 个整数。第 $$$i$$$ 行包含整数 $$$dx_i$$$、$$$dy_i$$$ 和 $$$K_i$$$。 ($$$-10^9 \leq dx_i, dy_i \leq 10^9$$$, $$$1 \leq K_i \leq N$$$)

输出

对于每个 $$$Q$$$ 决赛入围者,在单独的行中打印最后弹出的气泡的索引。

示例

输入 #1

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

输出 #1

4
2

输入 #2

4
1 1
2 2
7 1
1 7
3
2 2 1
1 -5 4
-6 5 3

输出 #2

3
2
3

注意

有两名决赛入围者愿意玩泡泡。如果第一名决赛入围者玩气泡,则坐标 (0, 0)、(1, 0) 和 (1, 1) 处的气泡将按顺序弹出。他们的索引分别是 1、2 和 4,所以答案是 4。如果第二个决赛入围者玩气泡,那么坐标 (1, 1)、(0, 1)、(0, 0) 和 (1, 0) 处的气泡将按顺序弹出,所以答案是 2。

可视化:链接。