CF1599D Bubble Popping

在一个坐标平面上有 $N$ 个气泡。气泡非常小，可以认为每个气泡是一个点 $(X_i, Y_i)$。 有 $Q$ 位 Bubble Cup 决赛选手打算用这些气泡来玩游戏。每位选手会使用一根无限长的 Bubble Cup 棍子来戳破一些气泡。第 $i$ 位选手希望将棍子放在向量 $(dx_i, dy_i)$ 的方向上，并进行如下游戏，直到戳破 $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$，对于 $i \neq j$，$(X_i, Y_i) \neq (X_j, Y_j)$） 接下来一行包含一个整数 $Q$，表示有多少位选手参与游戏。（$1 \leq Q \leq 10^5$） 接下来的 $Q$ 行，每行包含三个整数，第 $i$ 行为 $dx_i$、$dy_i$ 和 $K_i$。（$-10^9 \leq dx_i, dy_i \leq 10^9$，$1 \leq K_i \leq N$）

对于每位选手，输出最后被戳破的气泡的编号，每行一个。

有两位选手参与游戏。如果第一位选手玩游戏，坐标为 $(0, 0)$、$(1, 0)$ 和 $(1, 1)$ 的气泡会依次被戳破。它们的编号分别为 1、2 和 4，所以答案是 4。如果第二位选手玩游戏，坐标为 $(1, 1)$、$(0, 1)$、$(0, 0)$ 和 $(1, 0)$ 的气泡会依次被戳破，所以答案是 2。 可视化：[链接](https://petljamediastorage.blob.core.windows.net/uploads/example1.gif)。 由 ChatGPT 4.1 翻译