{"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't shrink or grow eventually.\"\n\n\"Everything is transient in a way and perennial in another.\"\n\nKanno 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.\n\nGazing 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.\n\nKanno 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:\n\n1.  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.\n2.  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$).\n\nThere 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\n## Input\n\nThe first line contains a positive integer $n$ ($2 \\leq n \\leq 200$) — the number of points in $S$.\n\nThe $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.\n\nThe next line contains a positive integer $q$ ($1 \\leq q \\leq 200$) — the number of queries.\n\nEach 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\n## Output\n\nOutput $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$.\n\nYour 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}$.\n\nFormally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $|a - b| \\le 10^{-6}$.\n\n[samples]\n\n## Note\n\nThe points in $S$ and possible candidates for line $l$ are depicted in the following figure.\n\n<center>![image](https://espresso.codeforces.com/6c2ba01b2152ec7547d51794da9141f0cb7d47e9.png)</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$.\n\nFor 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$.","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$，则不将其加入 $S$。随后，按以下顺序重复执行若干次操作（统称为一次 _移动_）：\n\n共有 $q$ 个查询，每个查询包含两个整数 $(t_i, m_i)$。对于每个查询，你需要帮助 Kanno 通过合理选择起始点 $P$，最大化经过 $m_i$ 次移动后停止位置为 $S$ 中第 $t_i$ 个点的概率，并输出该最大概率。注意，根据规则 1，$P$ 必须位于至少一条经过 $S$ 中至少两个点的直线上。\n\n第一行包含一个正整数 $n$（$2 lt.eq n lt.eq 200$）——集合 $S$ 中的点数。\n\n接下来的 $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)$。\n\n下一行包含一个正整数 $q$（$1 lt.eq q lt.eq 200$）——查询的数量。\n\n接下来的 $q$ 行中，每行包含两个用空格分隔的整数 $t$ 和 $m$（$1 lt.eq t_i lt.eq n$，$1 lt.eq m_i lt.eq 10^4$）——分别表示目标点的索引和移动次数。\n\n请输出 $q$ 行，每行一个十进制数——第 $i$ 行表示在适当选择起始点 $P$ 的前提下，经过 $m_i$ 步后停在第 $t_i$ 个点的最大概率。\n\n你的答案若与标准答案的每个数值之差的绝对值不超过 $10^(-6)$，则被视为正确。\n\n形式化地，设你的答案为 $a$，标准答案为 $b$，当且仅当 $| a -b | lt.eq 10^(-6)$ 时，你的答案被视为正确。\n\n集合 $S$ 中的点以及可能的直线 $l$ 的候选如图所示。\n\n对于第一个查询，当 $P = (-1, -3)$ 时，直线 $l$ 唯一确定为 $3 x = y$，因此 Kanno 以概率 $frac(1, 2)$ 移动到 $(0, 0)$。\n\n对于第三个查询，当 $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)$。\n\n## Input\n\n第一行包含一个正整数 $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$）——分别表示目标点的索引和移动次数。\n\n## Output\n\n请输出 $q$ 行，每行一个十进制数——第 $i$ 行表示在适当选择起始点 $P$ 的前提下，经过 $m_i$ 步后停在第 $t_i$ 个点的最大概率。你的答案若与标准答案的每个数值之差的绝对值不超过 $10^(-6)$，则被视为正确。形式化地，设你的答案为 $a$，标准答案为 $b$，当且仅当 $| a -b | lt.eq 10^(-6)$ 时，你的答案被视为正确。\n\n[samples]\n\n## Note\n\n集合 $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)$。","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 two points of $ S $.\n\nFor 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:\n$$\n\\mathcal{L}_P = \\{ \\ell \\in \\mathcal{L} \\mid P \\in \\ell \\}.\n$$\n\nFor 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:\n\n- 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.\n- 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.\n\nLet $ 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).\n\nLet $ \\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:\n- 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 $.\n- If $ P \\in S $: $ \\mathbf{v}_0[i] = \\delta_{i,k} $ if $ P = p_k $, then transitioned via above rule.\n\nFor each query $ (t_i, m_i) $, the goal is to compute:\n$$\n\\max_{P \\in \\bigcup_{\\ell \\in \\mathcal{L}} \\ell} \\left( \\mathbf{v}_{m_i}[t_i] \\right),\n$$\nwhere $ \\mathbf{v}_{m_i} = \\mathbf{v}_0 \\cdot T^{m_i} $, and $ \\mathbf{v}_0 $ is induced by $ P $.\n\nThe 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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF989E","tags":["dp","geometry","matrices","probabilities"],"sample_group":[["5\n0 0\n1 3\n2 2\n3 1\n4 4\n10\n1 1\n2 1\n3 1\n4 1\n5 1\n3 2\n3 3\n3 4\n3 5\n3 6","0.50000000000000000000\n0.50000000000000000000\n0.33333333333333331483\n0.50000000000000000000\n0.50000000000000000000\n0.18518518518518517491\n0.15226337448559670862\n0.14494741655235482414\n0.14332164812274550414\n0.14296036624949901017"]],"created_at":"2026-03-03 11:00:39"}}