← 返回题目列表

Codeforces · 989/E

E. 黄昏的恍惚

中文机器翻译题面 查看原题

坐标平面上有一组 $$$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)$$$。