A11813. A Trance of Nightfall
编程题
普及/提高-
知识点
题目描述
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.
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 $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}$ .
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}$ .
输出格式
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$ .
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$ .
输入输出样例
输入 #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
说明/提示
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$ .
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$ .