CF989E.A Trance of Nightfall

The cool breeze blows gently, the flowing water ripples steadily.

"Flowing and passing like this, the water isn't gone ultimately; Waxing and waning like that, the moon doesn't shrink or grow eventually."

"Everything is transient in a way and perennial in another."

Kanno doesn't seem to make much sense out of Mino's isolated words, but maybe it's time that they enjoy the gentle breeze and the night sky — the inexhaustible gifts from nature.

Gazing into the sky of stars, Kanno indulges in a night's tranquil dreams.

There is a set $S$ of $n$ points on a coordinate plane.

Kanno starts from a point $P$ that can be chosen on the plane. $P$ is not added to $S$ if it doesn't belong to $S$. Then the following sequence of operations (altogether called a move) is repeated several times, in the given order:

1. Choose a line $l$ such that it passes through at least two elements in $S$ and passes through Kanno's current position. If there are multiple such lines, one is chosen equiprobably.
2. Move to one of the points that belong to $S$ and lie on $l$. The destination is chosen equiprobably among all possible ones, including Kanno's current position (if it does belong to $S$).

There are $q$ queries each consisting of two integers $(t_i, m_i)$. For each query, you're to help Kanno maximize the probability of the stopping position being the $t_i$-th element in $S$ after $m_i$ moves with a proper selection of $P$, and output this maximum probability. Note that according to rule 1, $P$ should belong to at least one line that passes through at least two points from $S$.

凉爽的微风轻轻吹拂，潺潺流水缓缓泛起涟漪。

“逝者如斯，而未尝往也；盈虚者如彼，而卒莫消长也。”

“万物皆有其暂存之相，亦有其恒常之性。”

贯野难以从美浓这零散的言语中领悟深意，但或许此刻正该静享这和煦微风与浩瀚夜空——大自然取之不竭的馈赠。

仰望繁星点点的夜空，贯野沉醉于一晚宁静的梦境之中。

平面上给定一个包含 $n$ 个点的集合 $S$。

贯野从平面上任选一点 $P$ 出发（若 $P \notin S$，则不将其加入 $S$）。随后，按如下顺序重复执行以下一系列操作（统称为一次“移动”）若干次：

1. 选择一条直线 $l$，使得 $l$ 至少经过 $S$ 中两个点，且经过贯野当前所在位置。若满足条件的直线有多条，则等概率地从中任选一条。
2. 移动至 $l$ 上属于 $S$ 的某一点。所有可能的目的地点（包括贯野当前所在位置，若其本身属于 $S$）被等概率地选为终点。

共有 $q$ 个询问，每个询问由两个整数 $(t_i, m_i)$ 构成。对每个询问，你需要帮助贯野选择适当的初始点 $P$，以最大化经过 $m_i$ 次移动后停在 $S$ 中第 $t_i$ 个点的概率，并输出该最大概率。注意：根据规则 1，所选初始点 $P$ 必须至少位于一条经过 $S$ 中至少两个点的直线上。

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.

第一行包含一个正整数 $n$（$2 \leq n \leq 200$）——集合 $S$ 中点的个数。

接下来的 $n$ 行中，第 $i$ 行包含两个用空格分隔的整数 $x_i$ 和 $y_i$（$-10^4 \leq x_i, y_i \leq 10^4$）——表示集合 $S$ 中第 $i$ 个点的坐标。输入保证对所有满足 $1 \leq i \lt j \leq n$ 的 $i,j$，均有 $(x_i, y_i) \neq (x_j, y_j)$。

下一行包含一个正整数 $q$（$1 \leq q \leq 200$）——查询的个数。

接下来的 $q$ 行中，每行包含两个用空格分隔的整数 $t$ 和 $m$（$1 \leq t_i \leq n$，$1 \leq m_i \leq 10^4$）——分别表示目标点的索引和移动步数。

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}$.

输出 $q$ 行，每行包含一个十进制数——其中第 $i$ 行表示：在经过 $m_i$ 步后，停留在第 $t_i$ 个点上的最大概率（可通过适当选择起始位置 $P$ 实现）。

若你输出的每个数字与评测组答案中对应数字的差值均不超过 $10^{-6}$，则你的答案视为正确。

形式化地，设你的答案为 $a$，评测组答案为 $b$。当且仅当 $|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$.

集合 $S$ 中的点以及直线 $l$ 的可能候选如以下图所示。

对于第一个查询，当 $P = (-1, -3)$ 时，直线 $l$ 唯一确定为 $3x = y$，因此 Kanno 将以概率 $\frac{1}{2}$ 移动到 $(0, 0)$。

对于第三个查询，当 $P = (2, 2)$ 时，直线 $l$ 在 $x + y = 4$ 和 $x = y$ 之间等概率选取。随后，Kanno 将以概率 $\frac{1}{2} \cdot \frac{1}{3} = \frac{1}{6}$ 分别移动到其余四个点中的每一个，或以概率 $\frac{1}{3}$ 保持在 $(2, 2)$ 处不动。