En una mesa infinita, se te dan dos puntos distintos $A = (A_x, A_y)$ y $B = (B_x, B_y)$.
También tienes $M$ palos, cada uno de los cuales es un segmento de recta de longitud $W$. Puedes colocar estos palos en cualquier lugar de la mesa, con cualquier posición y orientación. Se permite que los palos se superpongan. Sin embargo, ningún palo puede contener el punto $A$ ni el punto $B$.
Una hormiga comienza en $A$ y quiere llegar a $B$. Puede caminar por cualquier lugar de la mesa, excepto que no puede cruzar ningún palo.
Quieres colocar los palos de modo que la longitud del camino más corto para la hormiga desde $A$ hasta $B$ sea lo más grande posible.
Si es posible bloquear a la hormiga por completo de modo que no exista ningún camino desde $A$ hasta $B$, la respuesta es $-1$.
En caso contrario, sea $L$ el supremo$^\dagger$ de las longitudes de los caminos más cortos desde $A$ hasta $B$ sobre todas las colocaciones válidas de los palos. Si existe una colocación que alcanza este valor, $L$ es simplemente el máximo. Si ninguna colocación individual lo alcanza, pero las colocaciones pueden acercarse arbitrariamente, aun así debes imprimir $L$.
$^\dagger$ El supremo (menor cota superior) de un conjunto de números reales es el menor número real que es mayor o igual que cada valor del conjunto. Puede ser alcanzado o no por un valor del conjunto.
Entrada
La entrada se proporciona en el siguiente formato:
T A_x A_y B_x B_y M W ...
- Todos los valores de entrada son enteros.
- $1 \le T \le 10^4$
- $0 \le A_x, A_y, B_x, B_y \le 10^9$
- $1 \le M, W \le 10^9$
- Se garantiza que $(A_x, A_y) \ne (B_x, B_y)$.
Salida
Para cada caso de prueba:
- Imprime $-1$ si la hormiga puede ser bloqueada por completo;
- En caso contrario, imprime un único número real — el valor $L$ definido anteriormente.
Sea $X$ la respuesta correcta e $Y$ tu salida. Tu salida se considera correcta si y solo si $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.
Ejemplo
Entrada 1
2 0 0 1 1 343 434 4 5 786331192 707731892 1 639711202
Salida 1
-1 1425074478.231629371643066
Nota
Caso de prueba 1: Se puede demostrar que al colocar los palos de forma óptima, la hormiga puede ser bloqueada por completo.