Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 2048 MB 总分: 100 难度: [显示] 可 Hack ✓
统计

Cai, el destacado multimillonario, tiene una obsesión muy particular: solo se siente cómodo cuando sus pies están firmemente plantados sobre un borde o vértice del embaldosado — es decir, sobre el contorno de alguna baldosa del suelo. Recientemente, adquirió una colección de baldosas triangulares idénticas de alta gama. Planea usar estas baldosas para embaldosar un pasillo largo y recto en su nueva mansión.

El pasillo es una franja infinita en un plano bidimensional. Para asegurar que el diseño cumpla con sus estándares supremos, Cai ha dictado una regla estricta de embaldosado: cada baldosa triangular debe colocarse de manera que abarque todo el ancho del pasillo, tocando ambas líneas paralelas de límite. Esto crea una teselación continua de una sola fila en la franja. Una de estas baldosas debe coincidir exactamente con su triángulo de referencia favorito, y todas las demás baldosas deben ser congruentes con él.

Cai se encuentra actualmente en una ubicación fija en el pasillo. Está agotado después de un largo día de trabajo de terraformación y, francamente, no se moverá en absoluto. Quiere que las baldosas se extiendan automáticamente por el suelo comenzando desde su triángulo de referencia, siempre que el patrón resultante siga sus reglas. ¡Por supuesto, solo será un éxito si un borde o vértice de las baldosas coincide con su posición actual!

Tu tarea es determinar si es posible embaldosar el pasillo de tal manera que la posición actual de Cai, el punto $D$, se encuentre exactamente sobre un borde o un vértice de la teselación que contiene a $\triangle ABC$. Los límites del pasillo se definen como las dos únicas líneas paralelas $l_1$ y $l_2$ tales que $l_1$ pasa por $A$ y $B$, y $l_2$ pasa por $C$. Una teselación de la franja formada por $(l_1, l_2)$ es un recubrimiento de toda la franja utilizando copias congruentes del triángulo $\triangle ABC$ (permitiendo traslación, rotación y reflexión), sin superposiciones ni huecos.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Ilustración de los dos primeros casos de prueba de ejemplo.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^3$) que indica el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene dos enteros $x_a$ e $y_a$ ($-100 \le x_a, y_a \le 100$), las coordenadas del punto $A$.

La segunda línea contiene dos enteros $x_b$ e $y_b$ ($-100 \le x_b, y_b \le 100$), las coordenadas del punto $B$.

La tercera línea contiene dos enteros $x_c$ e $y_c$ ($-100 \le x_c, y_c \le 100$), las coordenadas del punto $C$.

La cuarta línea contiene dos fracciones $x_{d1}/x_{d2}$ e $y_{d1}/y_{d2}$, donde $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ son enteros que satisfacen $-10^7 < x_{d1}, y_{d1} < 10^7$ y $0 < x_{d2}, y_{d2} < 10^7$, que representan las coordenadas del punto $D$.

Se garantiza que $A$, $B$ y $C$ forman un triángulo no degenerado.

Salida

Para cada caso de prueba, imprime "Yes" en una línea si existe una teselación válida tal que el punto $D$ se encuentre en un borde o un vértice de al menos un triángulo en el patrón. De lo contrario, imprime "No".

Ejemplos

Entrada 1

4
-2 1
0 0
0 2
2/1 0/1
-2 1
0 0
0 2
1/1 0/1
0 1
-2 1
0 2
1/2 7/4
0 1
-2 1
0 2
-3/2 3/4

Salida 1

Yes
No
Yes
No

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.