Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 2048 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Cai, den enastående miljardären, har en mycket speciell besatthet: han känner sig bara bekväm när hans fötter står stadigt på en kant eller ett hörn av plattsättningen — det vill säga på randen av någon golvplatta. Nyligen förvärvade han en samling identiska, exklusiva triangulära golvplattor. Han planerar att använda dessa plattor för att lägga golv i en lång, rak korridor i sin nya herrgård.

Korridoren är ett oändligt band i ett tvådimensionellt plan. För att säkerställa att designen uppfyller hans högsta krav har Cai dikterat en strikt plattsättningsregel: varje enskild triangulär platta måste placeras så att den spänner över hela korridorens bredd och vidrör båda de parallella gränslinjerna. Detta skapar en sammanhängande, enradig tessellering av bandet. En av dessa plattor måste exakt matcha hans favoritreferenstriangel, och alla andra plattor måste vara kongruenta med den.

Cai står för närvarande på en fast plats i korridoren. Han är utmattad efter en lång dag av terraformningsarbete och kommer, ärligt talat, inte att röra sig alls. Han vill att plattorna ska växa fram automatiskt över golvet med start från hans referenstriangel, så länge det resulterande mönstret följer hans regler. Naturligtvis är det bara en framgång om en kant eller ett hörn på plattorna sammanfaller med hans nuvarande position!

Din uppgift är att avgöra om det är möjligt att lägga plattor i korridoren så att Cais nuvarande position, punkten $D$, ligger exakt på en kant eller ett hörn av tesselleringen som innehåller $\triangle ABC$. Korridorens gränser definieras som de två unika parallella linjerna $l_1$ och $l_2$ sådana att $l_1$ går genom $A$ och $B$, och $l_2$ går genom $C$. En tessellering av bandet som bildas av $(l_1, l_2)$ är en plattsättning av hela bandet med kongruenta kopior av triangeln $\triangle ABC$ (där translation, rotation och spegling är tillåtna), utan överlappningar och utan glipor.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Illustration av de två första exempeltestfallen.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett heltal $T$ ($1 \le T \le 10^3$) som anger antalet testfall. För varje testfall:

Den första raden innehåller två heltal $x_a$ och $y_a$ ($-100 \le x_a, y_a \le 100$), koordinaterna för punkten $A$.

Den andra raden innehåller två heltal $x_b$ och $y_b$ ($-100 \le x_b, y_b \le 100$), koordinaterna för punkten $B$.

Den tredje raden innehåller två heltal $x_c$ och $y_c$ ($-100 \le x_c, y_c \le 100$), koordinaterna för punkten $C$.

Den fjärde raden innehåller två bråk $x_{d1}/x_{d2}$ och $y_{d1}/y_{d2}$, där $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ är heltal som uppfyller $-10^7 < x_{d1}, y_{d1} < 10^7$ och $0 < x_{d2}, y_{d2} < 10^7$, vilka representerar koordinaterna för punkten $D$.

Det garanteras att $A$, $B$ och $C$ bildar en icke-degenererad triangel.

Utdata

För varje testfall, skriv ut "Yes" på en rad om det finns en giltig tessellering sådan att punkten $D$ ligger på en kant eller ett hörn av minst en triangel i mönstret. Skriv annars ut "No".

Exempel

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