Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 2048 MB 총점: 100 난이도: [표시] 해킹 가능 ✓
통계

Cai, wybitny miliarder, ma bardzo szczególną obsesję: czuje się komfortowo tylko wtedy, gdy jego stopy stoją pewnie na krawędzi lub wierzchołku parkietu — to znaczy na brzegu pewnej płytki podłogowej. Niedawno nabył kolekcję identycznych, luksusowych trójkątnych płytek podłogowych. Planuje użyć tych płytek do wyłożenia długiego, prostego korytarza w swojej nowej rezydencji.

Korytarz jest nieskończonym pasem na płaszczyźnie dwuwymiarowej. Aby upewnić się, że projekt spełnia jego najwyższe standardy, Cai podyktował surową zasadę układania płytek: każda pojedyncza trójkątna płytka musi być umieszczona tak, aby rozciągała się na całą szerokość korytarza, dotykając obu równoległych linii brzegowych. Tworzy to ciągłą, jednorzędową teselację (parkietaż) pasa. Jedna z tych płytek musi dokładnie pokrywać się z jego ulubionym trójkątem wzorcowym, a wszystkie pozostałe płytki muszą być do niego przystające.

Cai stoi obecnie w stałym miejscu na korytarzu. Jest wyczerpany po długim dniu prac terraformacyjnych i, szczerze mówiąc, w ogóle nie zamierza się ruszać. Chce, aby płytki automatycznie rozrosły się po podłodze, zaczynając od jego trójkąta wzorcowego, o ile powstały wzór będzie zgodny z jego zasadami. Oczywiście sukcesem będzie tylko sytuacja, gdy krawędź lub wierzchołek płytek pokryje się z jego obecną pozycją!

Twoim zadaniem jest ustalenie, czy można wyłożyć korytarz płytkami tak, aby obecna pozycja Caia, punkt $D$, leżała dokładnie na krawędzi lub wierzchołku teselacji zawierającej $\triangle ABC$. Brzegi korytarza są zdefiniowane jako dwie jednoznacznie wyznaczone proste równoległe $l_1$ i $l_2$ takie, że $l_1$ przechodzi przez $A$ i $B$, a $l_2$ przechodzi przez $C$. Teselacja pasa utworzonego przez $(l_1, l_2)$ to pokrycie całego pasa za pomocą przystających kopii trójkąta $\triangle ABC$ (dopuszczając przesunięcia, obroty i odbicia), bez nakładania się i bez luk.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Ilustracja pierwszych dwóch przykładowych przypadków testowych.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^3$) oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy wiersz zawiera dwie liczby całkowite $x_a$ oraz $y_a$ ($-100 \le x_a, y_a \le 100$), współrzędne punktu $A$.

Drugi wiersz zawiera dwie liczby całkowite $x_b$ oraz $y_b$ ($-100 \le x_b, y_b \le 100$), współrzędne punktu $B$.

Trzeci wiersz zawiera dwie liczby całkowite $x_c$ oraz $y_c$ ($-100 \le x_c, y_c \le 100$), współrzędne punktu $C$.

Czwarty wiersz zawiera dwa ułamki $x_{d1}/x_{d2}$ oraz $y_{d1}/y_{d2}$, gdzie $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ są liczbami całkowitymi spełniającymi $-10^7 < x_{d1}, y_{d1} < 10^7$ oraz $0 < x_{d2}, y_{d2} < 10^7$, reprezentującymi współrzędne punktu $D$.

Zagwarantowane jest, że punkty $A$, $B$ i $C$ tworzą niezdegenerowany trójkąt.

Wyjście

Dla każdego przypadku testowego wypisz w jednym wierszu "Yes", jeśli istnieje poprawna teselacja taka, że punkt $D$ leży na krawędzi lub wierzchołku co najmniej jednego trójkąta we wzorze. W przeciwnym razie wypisz "No".

Przykłady

Wejście 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

Wyjście 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.