N - New Combination

Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)

You are given a set $P$ with $n$ points in the 2-dimensional plane. We want to know if a point $w$ can be written as a linear combination of points from $R$, where $R \subseteq P$, that is:

$w = \displaystyle\sum_{i=1}^{|R|} {\mu}_i \cdot R_i$

such that ${\mu}_i \ge 0$ for $i = 1,2,...,|R|$ and $\displaystyle\sum_{i=1}^{|R|} {\mu}_i = 1$.

For each point $w$ you should find a set $R$ with at most 5 elements ($|R| \le 5$) such that coefficients satisfy previous rule, or tell if such representation doesn't exist..


  • Let $p = (x, y)$ be a point and $c$ a real number. The product $c \cdot p$ is defined as point $s = (c \cdot x, c \cdot y)$.
  • Let $p_1 = (x_1, y_1)$ and $p_2 = (x_2, y_2)$ be two points. The sum $p_1 + p_2$ is defined as point $s = (x_1 + x_2, y_1 + y_2)$.


´╗┐First line of input contains an integer $n$ $(1 \leq n \leq 10^5)$, the number of points in $P$.

Next $n$ lines contains two integers $x_i, y_i$ $(0 \le x_i, y_i \le 10^9)$, the coordinates of the $i$-th point.

Next line contains an integer $q$ $(1 \le q \le 10^4)$, representing the amount of points $w$ to answer.

The remaining $q$ lines contains two integers $x_w, y_w(0 \le x_w, y_w \le 10^9)$, the coordinates of each point $w$.


For each point $w$:

  •  If there is no way to represent $w$ as described, print the word "impossible" (without the quotes).
  •  If there is a solution, print a line with an integer $m$, indicating the amount of elements in $R$. 

Then print $m$ lines, each of them with an integer $i$ indicating that the $i$-th point of $P$ belongs to $R$, followed by a real number $\mu_i$ indicating its coefficient.

Note: Your solution will be considered correct if it follows all the described restrictions and the squared distance between $w$ and the point $w' = \displaystyle\sum_{i=1}^{|R|} {\mu}_i \cdot R_i$ obtained does not exceed $10^{-5}$.

Sample test(s)

6 0 0 2 0 4 1 0 2 2 2 3 3 3 1 1 2 1 3 0
4 1 0.25 2 0.25 4 0.25 5 0.25 3 1 0.44444444444444444444 3 0.33333333333333333332 6 0.22222222222222222223 impossible
2 1 3 5 3 3 4 2 3 3 8 3
impossible 2 1 0.5 2 0.5 impossible