Por Nacho Cabanes
Nivel de dificultad aproximado (1 a 5): 3
Se está estudiando un enjambre de N luciérnagas. Cada luciérnaga se mueve en línea recta a velocidad constante. Usted se encuentra en el centro del universo, en la posición (0, 0, 0). Todas las luciérnagas tienen la misma masa, y se desea saber a qué distancia mínima desde su ubicación (el origen de coordenadas) se llega a encontrar el centro del enjambre.
Se conoce la posición y la velocidad de cada luciérnaga en t = 0, y pero sólo se está interesados en instantes t >= 0. Las luciérnagas tienen velocidad constante, y pueden moverse libremente a través de todo el espacio. Siendo M(t) la ubicación del centro de masa de las luciérnagas N en el momento t, d(t) la distancia entre su posición y M(t) en el instante t. Debe encontrar el valor mínimo de d(t), Dmin
Entrada
La primera línea de entrada contiene un único entero T, el número de casos de prueba. Cada caso de prueba se inicia con una línea que contiene un entero N, la cantidad de luciérnagas, seguido por N líneas de la forma
x y z vx vy vz
Cada una de estas líneas se describe una luciérnaga: (x, y, z) es su posición inicial en el instante t = 0, y (vx, vy, vz) es su velocidad.
Salida
Para cada caso de prueba, la salida será
Case #X: dmin tmín
donde X es el número de caso de prueba, a partir de 1. Cualquier respuesta con un error absoluto o relativo de un máximo de 10-5, serán aceptable.
Límites
Todos los números en la entrada serán enteros.
1 <= t <= 100
Los valores de x, y, z, vx, vy y vz será entre -5000 y 5000, ambos inclusive.
Conjunto de datos pequeño
3 <= n <= 10
Conjunto de datos grande
3 <= n <= 500
(Asegúrate de que has leído las preguntas frecuentes antes de plantear tu solución)
Entrada
3
3
3 -4 0 0 0 3
-3 -2 -1 3 0 0
-3 -1 2 0 3 0
3
-5 0 0 1 0 0
-7 0 0 1 0 0
-6 3 0 1 0 0
4
1 2 3 1 2 3
3 2 1 3 2 1
1 0 0 0 0 -1
0 10 0 0 -1 -10Salida
Caso #1: 0.00000000 1.00000000
Caso #2: 1.00000000 6.00000000
Caso #3: 3.36340601 1.00000000Notas
Teniendo en cuenta los puntos N (xi, yi, zi), su centro de masa es el punto (xc, yc, zc),que cumple:
xc = (x1 + x2 + ... + xn) / N
yc = (y1 + y2 + ... + yn) / N
zc = (z1 + z2 + ... + Zn) / N