CF1599D.Bubble Popping

There are $N$ bubbles in a coordinate plane. Bubbles are so tiny that it can be assumed that each bubble is a point $(X_i, Y_i)$.

$Q$ Bubble Cup finalists plan to play with the bubbles. Each finalist would link to use infinitely long Bubble Cup stick to pop some bubbles. The $i$-th finalist would like to place the stick in the direction of vector $(dxi, dyi)$, and plays the following game until $K_i$ bubbles are popped. The game starts with finalist placing the stick in the direction of vector $(dx_i, dy_i)$, and sweeping it from the infinity to the left until it hits some bubble, which is immediately popped. It is guaranteed that only one bubble will be hit in this step. After that the finalist starts rotating the stick in the counter clockwise direction with the center of rotation in point where the previous bubble was popped. When the next bubble is hit, it is immediately popped and becomes the new center of rotation. The process continues until $K_i$ bubbles have been popped. It is guaranteed that the stick won't hit two bubbles simultaneously in this process.

For each finalist find which bubble would be popped the last. Note that each game starts with the configuration of all $N$ bubbles, so the games don't depend on the previous games.

坐标平面上有 $N$ 个气泡。气泡非常微小，因此可将每个气泡视为一个点 $(X_i, Y_i)$。

共有 $Q$ 名 Bubble Cup 决赛选手计划与这些气泡进行游戏。每名选手将使用一根无限长的 Bubble Cup 棒来戳破若干气泡。第 $i$ 名选手希望将棒的方向设定为向量 $(dx_i, dy_i)$，并执行如下游戏，直至戳破 $K_i$ 个气泡为止：游戏开始时，选手将棒按向量 $(dx_i, dy_i)$ 的方向放置，并从无穷远处自左向右平移该棒，直到首次触碰到某个气泡——该气泡立即被戳破。题目保证此步骤中仅会触碰到一个气泡。随后，选手以刚被戳破的气泡所在位置为旋转中心，将棒逆时针旋转；当棒再次触碰到下一个气泡时，该气泡立即被戳破，并成为新的旋转中心。此过程持续进行，直至共戳破 $K_i$ 个气泡为止。题目保证在此过程中，棒不会同时触碰到两个气泡。

对每名选手，请找出其游戏中最后一个被戳破的气泡。注意：每轮游戏均从全部 $N$ 个气泡的初始配置开始，因此各轮游戏相互独立，互不影响。

The first line contains one integer $N$ — the number of bubbles. ($1 \leq N \leq 10^5$)

Each of the next $N$ lines contains two integers. The $i$-th line contains integers $X_i$ and $Y_i$ — the coordinates of the $i$-th bubble. ($-10^9 \leq X_i, Y_i \leq 10^9$, $(X_i, Y_i) \neq (X_j, Y_j)$ for $i \neq j$)

The next line contains one integer $Q$ — the number of finalists willing to play with the bubbles. ($1 \leq Q \leq 10^5$)

Each of the next Q lines contains 3 integers. The $i$-th line contains integers $dx_i$, $dy_i$ and $K_i$. ($-10^9 \leq dx_i, dy_i \leq 10^9$, $1 \leq K_i \leq 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$）

For each of the $Q$ finalists, print the index of the bubble which would be popped last, in the separate line.

对于每位 $Q$ 位决赛选手，分别输出最后被戳破的气泡的索引（每行一个）。

There are two finalists willing to play with the bubbles. If the first finalist plays with the bubbles, then the bubbles at coordinates (0, 0), (1, 0) and (1, 1) would be popped in that order. Their indexes are 1, 2 and 4, so the answer is 4. If the second finalist plays with the bubbles, then the bubbles at coordinates (1, 1), (0, 1), (0, 0) and (1, 0) would be popped in that order, so the answer is 2.

Visualization: link.

有两位决赛选手愿意玩泡泡游戏。如果第一位决赛选手玩泡泡，那么坐标为 $(0, 0)$、$(1, 0)$ 和 $(1, 1)$ 的泡泡将按此顺序被戳破。它们的编号分别为 $1$、$2$ 和 $4$，因此答案是 $4$。如果第二位决赛选手玩泡泡，那么坐标为 $(1, 1)$、$(0, 1)$、$(0, 0)$ 和 $(1, 0)$ 的泡泡将按此顺序被戳破，因此答案是 $2$。

示意图：link。