Center of Mass of a Firefly Swarm

You are watching a swarm of $N$ fireflies. Each firefly moves along a straight line at a constant speed. You stand at the origin $(0, 0, 0)$ of space. All fireflies have the same mass, and you want to know how close the center of the swarm comes to you.

You know the position and the velocity of every firefly at time $t = 0$, and only times $t \ge 0$ matter. Velocities never change, and a firefly passes freely through anything, including the other fireflies and you. Let $M(t)$ be the center of mass of the $N$ fireflies at time $t$, and let $d(t)$ be the distance between the origin and $M(t)$. Find the minimum value $d_{\min}$ of $d(t)$ over $t \ge 0$, and the earliest time $t_{\min}$ with $d(t_{\min}) = d_{\min}$.

The first line contains the number of test cases $T$. Each test case starts with a line holding the number of fireflies $N$, followed by $N$ lines of this form.

x y z vx vy vz

Each line describes one firefly. $(x, y, z)$ is its position at time $t = 0$ and $(v_x, v_y, v_z)$ is its velocity.

Limits

• Every number in the input is an integer.
• $1 \le T \le 100$
• $3 \le N \le 500$
• $-5000 \le x, y, z, v_x, v_y, v_z \le 5000$

For each test case print one line of this form.

Case #X: dmin tmin

$X$ is the test case number, starting from 1. Print $d_{\min}$ first, then a single space, then $t_{\min}$. Round both values to eight digits after the decimal point and print all eight digits, rounding an exact half up. The rounding has to be exact, and $t_{\min}$ can be larger than $10^6$, so double precision floating point alone may not carry enough digits.

The center of mass of $N$ points $(x_i, y_i, z_i)$ is the point $(x_c, y_c, z_c)$ below.

xc = (x1 + x2 + ... + xN) / N
yc = (y1 + y2 + ... + yN) / N
zc = (z1 + z2 + ... + zN) / N