Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 2048 MB Toplam puan: 100 Zorluk: [göster] Hack'lenebilir ✓
İstatistikler

Cai, den enestående milliardæren, har en veldig spesiell besettelse: han føler seg bare komfortabel når føttene hans er plantet godt på en kant eller et hjørne av flisleggingen — det vil si på grensen til en gulvflis. Nylig kjøpte han en samling identiske, eksklusive trekantede gulvfliser. Han planlegger å bruke disse flisene til å flislegge en lang, rett korridor i sitt nye herskapshus.

Korridoren er en uendelig stripe i et todimensjonalt plan. For å sikre at designet oppfyller hans øverste standarder, har Cai diktert en streng flisleggingsregel: hver eneste trekantede flis må plasseres slik at den spenner over hele korridorens bredde og berører begge de parallelle grenselinjene. Dette skaper en sammenhengende, én-rads tessellering av stripen. Én av disse flisene må passe nøyaktig med hans favoritt-referansetrekant, og alle andre fliser må være kongruente med den.

Cai står for øyeblikket på et fast sted i gangen. Han er utslitt etter en lang dag med terraformingsarbeid og vil, helt ærlig, ikke flytte seg i det hele tatt. Han vil at flisene skal vokse automatisk utover gulvet med start fra referansetrekanten hans, så lenge det resulterende mønsteret følger reglene hans. Selvfølgelig er det bare en suksess hvis en kant eller et hjørne av flisene sammenfaller med hans nåværende posisjon!

Din oppgave er å avgjøre om det er mulig å flislegge korridoren slik at Cais nåværende posisjon, punkt $D$, ligger nøyaktig på en kant eller et hjørne av tesselleringen som inneholder $\triangle ABC$. Korridorens grenser er definert som de to unike parallelle linjene $l_1$ og $l_2$ slik at $l_1$ går gjennom $A$ og $B$, og $l_2$ går gjennom $C$. En tessellering av stripen dannet av $(l_1, l_2)$ er en flislegging av hele stripen ved bruk av kongruente kopier av trekanten $\triangle ABC$ (som tillater translasjon, rotasjon og refleksjon), uten overlappinger og uten glipper.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Illustrasjon av de to første eksempeltesttilfellene.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^3$) som angir antall testtilfeller. For hvert testtilfelle:

Den første linjen inneholder to heltall $x_a$ og $y_a$ ($-100 \le x_a, y_a \le 100$), koordinatene til punkt $A$.

Den andre linjen inneholder to heltall $x_b$ og $y_b$ ($-100 \le x_b, y_b \le 100$), koordinatene til punkt $B$.

Den tredje linjen inneholder to heltall $x_c$ og $y_c$ ($-100 \le x_c, y_c \le 100$), koordinatene til punkt $C$.

Den fjerde linjen inneholder to brøker $x_{d1}/x_{d2}$ og $y_{d1}/y_{d2}$, der $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ er heltall som tilfredsstiller $-10^7 < x_{d1}, y_{d1} < 10^7$ og $0 < x_{d2}, y_{d2} < 10^7$, og representerer koordinatene til punkt $D$.

Det er garantert at $A$, $B$ og $C$ danner en ikke-degenerert trekant.

Utdata

For hvert testtilfelle skal du skrive ut "Yes" på en linje hvis det finnes en gyldig tessellering slik at punkt $D$ ligger på en kant eller et hjørne av minst én trekant i mønsteret. Ellers skal du skrive ut "No".

Eksempler

Inndata 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

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