Optimal Space Way

By the year 2180 AD, humanity has begun to leave Earth and settle in space. Thousands of space cities are built on a single imaginary plane so that they can all share one universal business hour, so the location of every city is a point $(x, y)$ on a two-dimensional Cartesian plane.

The cities lie far apart, and the only way to travel between them is by shuttle rocket. Because rockets are expensive, the space agency decides to build a single super space-way (SSW): one perfectly straight road that may extend without bound in both directions.

To travel from a city $c_1$ to a city $c_2$, a traveler flies by rocket from $c_1$ to the point of the SSW nearest to $c_1$, moves cheaply along the SSW, and then flies by rocket from the point of the SSW nearest to $c_2$ over to $c_2$. The nearest point of a straight line to a city is the foot of the perpendicular from the city to the line, so the rocket distance for a city equals its perpendicular distance to the SSW.

The cost of a rocket that flies a distance $v$ is $v^2$; travel along the SSW is comparatively free and is ignored. Every ordinary city sends and receives the same number of rocket flights per calendar year. You must place the SSW so that the total yearly rocket cost is as small as possible, and report the resulting minimum average cost per rocket flight.

Because every ordinary city has the same number of flights, the average cost per rocket flight is exactly the average of the squared perpendicular distances from the cities to the SSW, and you may choose the line that minimizes this average.

Sometimes exactly one city is marked as the super city, the center of all activity. A super city has $M$ times as many rocket flights (incoming plus outgoing) as an ordinary city, while every other city stays ordinary. In that case each city's squared perpendicular distance is weighted by its number of flights, and you report the minimum weighted average cost per rocket flight (the minimum of $\dfrac{\sum_i w_i, d_i^2}{\sum_i w_i}$ over all lines, where $d_i$ is the perpendicular distance of city $i$ to the line, $w_i = M$ for the super city, and $w_i = 1$ for every ordinary city).

Assumptions: the cities are points; the SSW is an infinitely thin straight line whose length may grow without bound in either direction whenever that lowers the cost; and every rocket flies in a straight line.

The input contains fewer than $50$ test cases.

Each test case begins with two integers $N$ and $Q$ ($0 < N \le 10000$, $0 < Q \le 100$), where $N$ is the number of space cities and $Q$ is the number of queries. Each of the next $N$ lines contains two floating-point numbers $x_i$ and $y_i$ ($0.0 \le x_i, y_i \le 1000.0$), the coordinates of the $i$-th city. Cities are numbered from $0$ to $N-1$ in the order they appear. Each of the next $Q$ lines contains two integers $S$ and $M$ ($0 \le S \le N-1$, $1 < M \le 10000$): city $S$ is the super city, and its total number of rocket flights is $M$ times that of an ordinary city.

A line containing two zeros terminates the input and must not be processed.

For each test case, print $Q + 2$ lines.

• The first line is Case k:, where $k$ is the test-case number starting from $1$.
• The second line is the minimum average cost per rocket flight when every city is ordinary.
• Each of the next $Q$ lines corresponds to one query, in the given order, and has the form i: value, where $i$ is the query number starting from $1$ and value is the minimum average cost per rocket flight when city $S$ of that query is the super city and every other city is ordinary.

Every cost must be printed with exactly five digits after the decimal point.