坐标平面上有一组 $$$S$$$ 个 $$$n$$$ 点。
Kanno 从平面上可以选择的点 $$$P$$$ 开始。如果 $$$P$$$ 不属于 $$$S$$$,则不会将其添加到 $$$S$$$。然后按照给定的顺序重复以下操作序列(统称为移动)多次:
1. 选择一条线 $$$l$$$,使其穿过 $$$S$$$ 中的至少两个元素,并穿过 Kanno 的当前位置。如果有多个这样的行,则等概率地选择一个。
2. 移动到属于 $$$S$$$ 并位于 $$$l$$$ 上的点之一。目的地是在所有可能的目的地中平均选择的,包括 Kanno 的当前位置(如果它确实属于 $$$S$$$)。
有 $$$q$$$ 查询,每个查询由两个整数 $$$(t_i, m_i)$$$ 组成。对于每个查询,您要帮助 Kanno 最大化 $$$m_i$$$ 移动后 $$$S$$$ 中停止位置为 $$$S$$$ 中第 $$$t_i$$$ 个元素的概率,并输出该最大概率。请注意,根据规则 1,$$$P$$$ 应该属于至少一条从 $$$S$$$ 穿过至少两个点的线。
输入
第一行包含一个正整数 $$$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$$$,$$$(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$$$) — 分别是目标点的索引和移动次数。
输出
输出 $$$q$$$ 行,每行包含一个十进制数 - 其中第 $$$i$$$ 表示在 $$$m_i$$$ 步之后停留在第 $$$t_i$$$ 个点上的最大概率,并正确选择起始位置 $$$P$$$。
如果您输出中的每个数字与陪审团答案中的相应数字最多相差 $$$10^{-6}$$$,则您的答案将被视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。如果 $$$|a - b| 则您的答案被认为是正确的\le 10^{-6}$$$。
示例
输入 #1
5 0 0 1 3 2 2 3 1 4 4 10 1 1 2 1 3 1 4 1 5 1 3 2 3 3 3 4 3 5 3 6
输出 #1
0.50000000000000000000 0.50000000000000000000 0.33333333333333331483 0.50000000000000000000 0.50000000000000000000 0.18518518518518517491 0.15226337448559670862 0.14494741655235482414 0.14332164812274550414 0.14296036624949901017
注意
$$$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)$$$。