Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

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.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.