Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 2048 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓
Statistiques

Cai, l'eccezionale miliardario, ha un'ossessione molto particolare: si sente a suo agio solo quando i suoi piedi sono ben piantati su un lato o un vertice della piastrellatura — cioè sul bordo di qualche piastrella del pavimento. Di recente ha acquistato una collezione di identiche piastrelle triangolari di alta gamma. Ha intenzione di utilizzare queste piastrelle per pavimentare un lungo corridoio rettilineo nella sua nuova villa.

Il corridoio è una striscia infinita su un piano bidimensionale. Per garantire che il design soddisfi i suoi standard supremi, Cai ha imposto una rigida regola di piastrellatura: ogni singola piastrella triangolare deve essere posizionata in modo da coprire l'intera larghezza del corridoio, toccando entrambe le linee di confine parallele. Ciò crea una tassellazione continua a fila singola della striscia. Una di queste piastrelle deve corrispondere esattamente al suo triangolo di riferimento preferito e tutte le altre piastrelle devono essere congruenti ad esso.

Cai si trova attualmente in una posizione fissa nel corridoio. È esausto dopo una lunga giornata di lavori di terraformazione e, francamente, non ha alcuna intenzione di muoversi. Vuole che le piastrelle si estendano automaticamente sul pavimento a partire dal suo triangolo di riferimento, purché il motivo risultante segua le sue regole. Naturalmente, sarà un successo solo se un lato o un vertice delle piastrelle coincide con la sua posizione attuale!

Il tuo compito è determinare se è possibile piastrellare il corridoio in modo che la posizione attuale di Cai, il punto $D$, giaccia esattamente su un lato o un vertice della tassellazione contenente $\triangle ABC$. I confini del corridoio sono definiti come le due uniche rette parallele $l_1$ e $l_2$ tali che $l_1$ passa per $A$ e $B$, e $l_2$ passa per $C$. Una tassellazione della striscia formata da $(l_1, l_2)$ è una piastrellatura dell'intera striscia mediante copie congruenti del triangolo $\triangle ABC$ (consentendo traslazione, rotazione e riflessione), senza sovrapposizioni e senza spazi vuoti.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Illustrazione dei primi due casi di test di esempio.

Input

Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^3$) che indica il numero di casi di test. Per ogni caso di test:

La prima riga contiene due interi $x_a$ e $y_a$ ($-100 \le x_a, y_a \le 100$), le coordinate del punto $A$.

La seconda riga contiene due interi $x_b$ e $y_b$ ($-100 \le x_b, y_b \le 100$), le coordinate del punto $B$.

La terza riga contiene due interi $x_c$ e $y_c$ ($-100 \le x_c, y_c \le 100$), le coordinate del punto $C$.

La quarta riga contiene due frazioni $x_{d1}/x_{d2}$ e $y_{d1}/y_{d2}$, dove $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ sono interi che soddisfano $-10^7 < x_{d1}, y_{d1} < 10^7$ e $0 < x_{d2}, y_{d2} < 10^7$, che rappresentano le coordinate del punto $D$.

È garantito che $A$, $B$ e $C$ formino un triangolo non degenere.

Output

Per ogni caso di test, stampa "Yes" su una riga se esiste una tassellazione valida tale che il punto $D$ giaccia su un lato o un vertice di almeno un triangolo nel motivo. Altrimenti, stampa "No".

Esempi

Input 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

Output 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.