Hubble Space Telescope

An astrophysicist observes a spiral galaxy, the Andromeda Galaxy, through the Hubble Space Telescope. He is interested in the motion of $n$ stars in the galaxy. Each star moves with constant velocity along a straight line in the telescope's picture. One of the $n$ stars is special and is named alpha. He wants to know the moment at which the maximum distance from alpha to the other $n - 1$ stars becomes as small as possible.

The picture is a two-dimensional Cartesian plane. Let $S = \{s_0, s_1, \dots, s_{n-1}\}$ be the set of $n$ stars, and let $s_0$ be the star alpha. Star $s_i$ moves along the trajectory $p_i + t\,v_i$ over time $t$, where $p_i = (x_i, y_i)$ is its position at time $0$ and $v_i = (a_i, b_i)$ is its velocity vector. The stars never actually collide: when two of them meet at a point they simply pass through each other.

Given the stars and their velocities, find the time $t$ with $0 \le t \le 10^5$ at which the maximum distance from alpha to the remaining stars is minimized. If several times achieve the same minimum, report the earliest one.

Figure 1 shows an example with $4$ stars. Each arrow is a star's velocity vector. In this example the maximum distance from alpha to the other $3$ stars is smallest at time $t = 3$.

(a) at time $t = 0$, and (b) at time $t = 3$.

Figure 1. An example.

The input is read from standard input. The first line contains the number of test cases $T$. Each test case starts with a line containing an integer $n$ ($2 \le n \le 50000$), the number of stars in $S$. Each of the next $n$ lines contains four integers $x_i$, $y_i$, $a_i$, $b_i$: the position $(x_i, y_i)$ of star $s_i$ at time $0$ and its velocity vector $(a_i, b_i)$, where $-200000 \le x_i, y_i \le 200000$ and $-500 \le a_i, b_i \le 500$. The first of these $n$ lines describes alpha ($s_0$). Two or more stars may share the same position at time $0$.

Write to standard output. For each test case, print on its own line the time in the range $0 \le t \le 10^5$ at which the maximum distance from alpha ($s_0$) to the other $n - 1$ stars is minimized, rounded to exactly four digits after the decimal point.