A11813 | A Trance of Nightfall

The first line contains a positive integer $n$ ( $2 \leq n \leq 200$ ) — the number of points in $S$ .

The $i$ -th of the following $n$ lines contains two space-separated integers $x_i$ and $y_i$ ( $-10^4 \leq x_i, y_i \leq 10^4$ ) — the coordinates of the $i$ -th point in $S$ . The input guarantees that for all $1 \leq i \lt j \leq n$ , $(x_i, y_i) \neq (x_j, y_j)$ holds.

The next line contains a positive integer $q$ ( $1 \leq q \leq 200$ ) — the number of queries.

Each of the following $q$ lines contains two space-separated integers $t$ and $m$ ( $1 \leq t_i \leq n$ , $1 \leq m_i \leq 10^4$ ) — the index of the target point and the number of moves, respectively.

Output $q$ lines each containing a decimal number — the $i$ -th among them denotes the maximum probability of staying on the $t_i$ -th point after $m_i$ steps, with a proper choice of starting position $P$ .

Your answer will be considered correct if each number in your output differs from the corresponding one in jury's answer by at most $10^{-6}$ .

Formally, let your answer be $a$ , and the jury's answer be $b$ . Your answer is considered correct if $|a - b| \le 10^{-6}$ .

The points in $S$ and possible candidates for line $l$ are depicted in the following figure.

For the first query, when $P = (-1, -3)$ , $l$ is uniquely determined to be $3x = y$ , and thus Kanno will move to $(0, 0)$ with a probability of $\frac 1 2$ .

For the third query, when $P = (2, 2)$ , $l$ is chosen equiprobably between $x + y = 4$ and $x = y$ . Kanno will then move to the other four points with a probability of $\frac 1 2 \cdot \frac 1 3 = \frac 1 6$ each, or stay at $(2, 2)$ with a probability of $\frac 1 3$ .