A Trance of Nightfall
Contest: Codeforces Round 487 (Div. 2)
Difficulty rating: 2700
Tags: dp, geometry, matrices, probabilities

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 format:
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 format:
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}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
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

Example output:
0.50000000000000000000
0.50000000000000000000
0.33333333333333331483
0.50000000000000000000
0.50000000000000000000
0.18518518518518517491
0.15226337448559670862
0.14494741655235482414
0.14332164812274550414
0.14296036624949901017

Editorial:
Is this a graph theory problem? Yes.
Let's consider a graph $$$G = (V, E)$$$, where there is a vertex for each point in $$$S$$$ (the terms "vertices" and "points" are used interchangeably hereafter), and an edge $$$(u, v)$$$ of weight $$$w$$$ whenever $$$v$$$ can be reached from $$$u$$$ in one move with a probability of $$$w$$$.
Finding out all the lines, removing duplicates, and building the graph can be done straightforwardly in $$$O(n^3)$$$ time.
Represent the graph as an adjacency matrix $$$A$$$. Now, given a fixed target vertex $$$t$$$, we'd like to calculate for each vertex $$$u$$$ the probability of reaching $$$t$$$ from $$$u$$$ after $$$m$$$ moves. Let $$${f^{(m)}}_u$$$ be this probability.
We can represent $$$f^{(m)}$$$ as an $$$n \times 1$$$ vector. Obviously $$$f^{(0)} = (0, \ldots, 0, 1, 0, \ldots, 0)^\mathrm{T}$$$, where only the $$$t$$$-th element is $$$1$$$. Here $$$v^\mathrm{T}$$$ denotes transpose of $$$v$$$.
It's not hard to see that $$${f^{(m)}}_u = \sum_{(u, v) \in E} A_{u, v} \cdot {f^{(m-1)}}_v$$$. Thus we can deduce that $$$f^{(m)} = A \cdot f^{(m-1)}$$$. By induction, $$$f^{(m)} = A^m \cdot f^{(0)}$$$.
In this way, for each query $$$(t, m)$$$, we can calculate $$$f^{(m-1)}$$$ in order to get for each $$$u$$$ the probability of reaching $$$t$$$ in $$$m - 1$$$ steps.
You may ask, why $$$m - 1$$$? It's because after the first move, the whole process can be determined by Kanno's position; but the first step is up to us to decide.
To be more precise, the process, therefore the desired probability, is determined after the $$$l$$$ in the first move has been chosen. We should observe that if we select a point from which there are multiple candidates of $$$l$$$, we can always select a point on one of the candidates, making it the only candidate without decreasing the whole probability. It's because the average of a set of numbers never exceeds the largest among them.
Hence, we've proved that we only need to consider cases where there is only one candidate for $$$l$$$, and such cases are always valid. For each $$$l$$$, we should calculate the average of $$${f^{(m-1)}}_u$$$ such that the $$$u$$$-th point lies on $$$l$$$. With $$$f^{(m-1)}$$$ calculated, this should take no more than $$$O(n^2)$$$ time.
Now, one last thing remains: how to calculate $$$f^{(m-1)}$$$ quickly?
We utilize a trick that a multiplication of an $$$n \times n$$$ matrix and an $$$n \times 1$$$ vector takes $$$O(n^2)$$$ time. With $$$A^{2^i}$$$ preprocessed for all non-negative integers $$$i \leq \log_2 m$$$ in $$$O(n^3 \log m)$$$ time, we can perform $$$O(\log m)$$$ matrix-vector multiplications in order to calculate $$$f^{(m-1)}$$$ in $$$O(n^2 \log m)$$$ time.
Overall, the time complexity for the problem is $$$O((n + q) \cdot n^2 \cdot \log m)$$$.
If anybody is ever too lazy (:P) to do the fast-exponentiation step, setting $$$m' = \min\{m, 100\}$$$ and applying $$$O(m)$$$ matrix-vector multiplications also work well with the error toleration.
Bonus. Think of this problem in other ways that do not work. What's the difference, and where do the redundant calculations lie?
Bonus. Is the problem solvable with matrix diagonalization?
Bonus. In theory or in practice, try to show that the errors do not accumulate quickly in the matrix exponentiation processes for this problem.