English · Original
Chinese · Translation
Formal · Original
%epigraph%%epigraphtext% _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._%endepigraphtext%%endepigraph%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$.
## Input
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
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}$.
[samples]
## Note
The points in $S$ and possible candidates for line $l$ are depicted in the following figure.
<center></center>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$.
"如水般流淌而过，水终未消逝；如月般盈亏更替，月终不增减。"
"万物皆有其短暂与永恒之面。"
Kanno 并未完全理解 Mino 的孤立言辞，但或许此刻，他们该享受轻柔的微风与夜空——大自然无尽的馈赠。
凝望着星空，Kanno 沉浸于一夜宁静的梦境之中。
在坐标平面上有一个包含 $n$ 个点的集合 $S$。
Kanno 从平面上一个可自由选择的点 $P$ 出发。若 $P$ 不属于 $S$，则不将其加入 $S$。随后，按以下顺序重复执行若干次操作（统称为一次 _移动_）：
共有 $q$ 个查询，每个查询包含两个整数 $(t_i, m_i)$。对于每个查询，你需要帮助 Kanno 通过合理选择起始点 $P$，最大化经过 $m_i$ 次移动后停止位置为 $S$ 中第 $t_i$ 个点的概率，并输出该最大概率。注意，根据规则 1，$P$ 必须位于至少一条经过 $S$ 中至少两个点的直线上。
第一行包含一个正整数 $n$（$2 lt.eq n lt.eq 200$）——集合 $S$ 中的点数。
接下来的 $n$ 行中，第 $i$ 行包含两个用空格分隔的整数 $x_i$ 和 $y_i$（$-10^4 lt.eq x_i, y_i lt.eq 10^4$）——表示 $S$ 中第 $i$ 个点的坐标。输入保证对所有 $1 lt.eq i lt j lt.eq n$，均有 $(x_i, y_i) eq.not (x_j, y_j)$。
下一行包含一个正整数 $q$（$1 lt.eq q lt.eq 200$）——查询的数量。
接下来的 $q$ 行中，每行包含两个用空格分隔的整数 $t$ 和 $m$（$1 lt.eq t_i lt.eq n$，$1 lt.eq m_i lt.eq 10^4$）——分别表示目标点的索引和移动次数。
请输出 $q$ 行，每行一个十进制数——第 $i$ 行表示在适当选择起始点 $P$ 的前提下，经过 $m_i$ 步后停在第 $t_i$ 个点的最大概率。
你的答案若与标准答案的每个数值之差的绝对值不超过 $10^(-6)$，则被视为正确。
形式化地，设你的答案为 $a$，标准答案为 $b$，当且仅当 $| a -b | lt.eq 10^(-6)$ 时，你的答案被视为正确。
集合 $S$ 中的点以及可能的直线 $l$ 的候选如图所示。
对于第一个查询，当 $P = (-1, -3)$ 时，直线 $l$ 唯一确定为 $3 x = y$，因此 Kanno 以概率 $frac(1, 2)$ 移动到 $(0, 0)$。
对于第三个查询，当 $P = (2, 2)$ 时，直线 $l$ 在 $x + y = 4$ 和 $x = y$ 之间等概率选择。Kanno 随后以概率 $frac(1, 2) dot.op frac(1, 3) = frac(1, 6)$ 分别移动到其他四个点，或以概率 $frac(1, 3)$ 停留在 $(2, 2)$。
## Input
第一行包含一个正整数 $n$（$2 lt.eq n lt.eq 200$）——集合 $S$ 中的点数。接下来的 $n$ 行中，第 $i$ 行包含两个用空格分隔的整数 $x_i$ 和 $y_i$（$-10^4 lt.eq x_i, y_i lt.eq 10^4$）——表示 $S$ 中第 $i$ 个点的坐标。输入保证对所有 $1 lt.eq i lt j lt.eq n$，均有 $(x_i, y_i) eq.not (x_j, y_j)$。下一行包含一个正整数 $q$（$1 lt.eq q lt.eq 200$）——查询的数量。接下来的 $q$ 行中，每行包含两个用空格分隔的整数 $t$ 和 $m$（$1 lt.eq t_i lt.eq n$，$1 lt.eq m_i lt.eq 10^4$）——分别表示目标点的索引和移动次数。
## Output
请输出 $q$ 行，每行一个十进制数——第 $i$ 行表示在适当选择起始点 $P$ 的前提下，经过 $m_i$ 步后停在第 $t_i$ 个点的最大概率。你的答案若与标准答案的每个数值之差的绝对值不超过 $10^(-6)$，则被视为正确。形式化地，设你的答案为 $a$，标准答案为 $b$，当且仅当 $| a -b | lt.eq 10^(-6)$ 时，你的答案被视为正确。
[samples]
## Note
集合 $S$ 中的点以及可能的直线 $l$ 的候选如图所示。对于第一个查询，当 $P = (-1, -3)$ 时，直线 $l$ 唯一确定为 $3 x = y$，因此 Kanno 以概率 $frac(1, 2)$ 移动到 $(0, 0)$。对于第三个查询，当 $P = (2, 2)$ 时，直线 $l$ 在 $x + y = 4$ 和 $x = y$ 之间等概率选择。Kanno 随后以概率 $frac(1, 2) dot.op frac(1, 3) = frac(1, 6)$ 分别移动到其他四个点，或以概率 $frac(1, 3)$ 停留在 $(2, 2)$。
Let $ S = \{ p_1, p_2, \dots, p_n \} $ be a set of $ n $ distinct points in $ \mathbb{R}^2 $.
Define $ \mathcal{L} $ as the set of all distinct lines in $ \mathbb{R}^2 $ that pass through at least two points of $ S $.
For any point $ P \in \bigcup_{\ell \in \mathcal{L}} \ell $, define the set of lines through $ P $ that contain at least two points of $ S $ as:
$$
\mathcal{L}_P = \{ \ell \in \mathcal{L} \mid P \in \ell \}.
$$
For each $ \ell \in \mathcal{L}_P $, let $ S_\ell = \ell \cap S $, and define the transition probability from $ P $ along $ \ell $ as uniform over $ S_\ell \setminus \{P\} $ if $ P \in S $, or over $ S_\ell $ if $ P \notin S $. Specifically:
- If $ P \notin S $: from $ P $, choose a line $ \ell \in \mathcal{L}_P $ uniformly at random, then move to a point in $ S_\ell $ uniformly at random.
- If $ P \in S $: from $ P $, choose a line $ \ell \in \mathcal{L}_P $ uniformly at random, then move to a point in $ S_\ell \setminus \{P\} $ uniformly at random.
Let $ T \in \mathbb{R}^{n \times n} $ be the transition matrix where $ T_{i,j} $ is the probability of moving from point $ p_i \in S $ to point $ p_j \in S $ in one move, under the above rule. Define $ T_{i,j} = 0 $ if $ i = j $ and $ p_i $ lies on no line with any other point (but by problem constraint, every point lies on at least one such line).
Let $ \mathbf{v}_m \in \mathbb{R}^n $ be the state vector after $ m $ moves, where $ \mathbf{v}_m[i] $ is the probability of being at $ p_i $. For a starting point $ P \in \bigcup \mathcal{L} $, define the initial distribution $ \mathbf{v}_0 \in \mathbb{R}^n $ as:
- If $ P \notin S $: $ \mathbf{v}_0[i] = \frac{1}{|\mathcal{L}_P|} \cdot \frac{1}{|S_\ell|} $ for each $ p_i \in S_\ell $, summed over $ \ell \in \mathcal{L}_P $.
- If $ P \in S $: $ \mathbf{v}_0[i] = \delta_{i,k} $ if $ P = p_k $, then transitioned via above rule.
For each query $ (t_i, m_i) $, the goal is to compute:
$$
\max_{P \in \bigcup_{\ell \in \mathcal{L}} \ell} \left( \mathbf{v}_{m_i}[t_i] \right),
$$
where $ \mathbf{v}_{m_i} = \mathbf{v}_0 \cdot T^{m_i} $, and $ \mathbf{v}_0 $ is induced by $ P $.
The maximum is taken over all possible starting positions $ P $ lying on at least one line in $ \mathcal{L} $, and the resulting probability of being at $ p_{t_i} $ after $ m_i $ transitions.
API Response (JSON)
{
"problem": {
"name": "E. A Trance of Nightfall",
"description": {
"content": "%epigraph%%epigraphtext% _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'",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF989E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "%epigraph%%epigraphtext% _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'...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "\"如水般流淌而过，水终未消逝；如月般盈亏更替，月终不增减。\"\n\n\"万物皆有其短暂与永恒之面。\"\n\nKanno 并未完全理解 Mino 的孤立言辞，但或许此刻，他们该享受轻柔的微风与夜空——大自然无尽的馈赠。\n\n凝望着星空，Kanno 沉浸于一夜宁静的梦境之中。\n\n在坐标平面上有一个包含 $n$ 个点的集合 $S$。\n\nKanno 从平面上一个可自由选择的点 $P$ 出发。若 $P$ 不属于 $S$...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ S = \\{ p_1, p_2, \\dots, p_n \\} $ be a set of $ n $ distinct points in $ \\mathbb{R}^2 $.\n\nDefine $ \\mathcal{L} $ as the set of all distinct lines in $ \\mathbb{R}^2 $ that pass through at least tw...",
"is_translate": false,
"language": "Formal"
}
]
}