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 velocity. You stand at the center of the universe, at position $(0, 0, 0)$. Every firefly has the same mass, and you want to know how close the center of the swarm gets to you.

You know the position and the velocity of every firefly at time $t = 0$, and only times $t \ge 0$ matter. The velocities never change, and the fireflies pass freely through all of space, including through each other and through you. Let $M(t)$ be the center of mass of the $N$ fireflies at time $t$, and let $d(t)$ be the distance between your position and $M(t)$. Find the minimum value $d_{min}$ of $d(t)$, and the earliest time $t_{min}$ at which $d(t) = d_{min}$.

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

x y z vx vy vz

Each of those lines 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$
• $-5000 \le x, y, z, v_x, v_y, v_z \le 5000$
• $3 \le N \le 10$

For each test case, print one line of the form

Case #X: dmin tmin

$X$ is the test case number, starting from 1. Print $d_{min}$ and $t_{min}$ each rounded to exactly eight digits after the decimal point, padded with zeros when a digit is missing. Round an exact halfway value up. Separate the two values with a single space.

Given $N$ points $(x_i, y_i, z_i)$, their center of mass is the point $(x_c, y_c, z_c)$ where

$x_c = \frac{x_1 + x_2 + \dots + x_N}{N}, \qquad y_c = \frac{y_1 + y_2 + \dots + y_N}{N}, \qquad z_c = \frac{z_1 + z_2 + \dots + z_N}{N}$