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, der herausragende Milliardär, hat eine ganz besondere Obsession: Er fühlt sich nur wohl, wenn seine Füße fest auf einer Kante oder Ecke des Fliesenmusters stehen — das heißt auf dem Rand einer Bodenfliese. Kürzlich erwarb er eine Kollektion identischer, hochwertiger dreieckiger Bodenfliesen. Er plant, mit diesen Fliesen einen langen, geraden Korridor in seiner neuen Villa zu fliesen.

Der Korridor ist ein unendlicher Streifen in einer zweidimensionalen Ebene. Um sicherzustellen, dass das Design seinen höchsten Ansprüchen genügt, hat Cai eine strenge Fliesenregel diktiert: Jede einzelne dreieckige Fliese muss so platziert werden, dass sie die gesamte Breite des Korridors überspannt und beide parallelen Begrenzungslinien berührt. Dies erzeugt eine durchgehende, einreihige Parkettierung (Tessellation) des Streifens. Eine dieser Fliesen muss genau mit seinem bevorzugten Referenzdreieck übereinstimmen, und alle anderen Fliesen müssen dazu kongruent sein.

Cai steht derzeit an einer festen Position im Flur. Er ist nach einem langen Tag voller Terraforming-Arbeiten erschöpft und wird sich, offen gesagt, überhaupt nicht bewegen. Er möchte, dass die Fliesen ausgehend von seinem Referenzdreieck automatisch über den Boden wachsen, solange das entstehende Muster seinen Regeln folgt. Natürlich ist es nur dann ein Erfolg, wenn eine Kante oder Ecke der Fliesen mit seiner aktuellen Position zusammenfällt!

Ihre Aufgabe ist es zu bestimmen, ob es möglich ist, den Korridor so zu fliesen, dass Cais aktuelle Position, Punkt $D$, genau auf einer Kante oder einer Ecke der Parkettierung liegt, die $\triangle ABC$ enthält. Die Grenzen des Korridors sind definiert als die zwei eindeutigen parallelen Geraden $l_1$ und $l_2$, sodass $l_1$ durch $A$ und $B$ verläuft und $l_2$ durch $C$ verläuft. Eine Parkettierung des durch $(l_1, l_2)$ gebildeten Streifens ist eine Überdeckung des gesamten Streifens mit kongruenten Kopien des Dreiecks $\triangle ABC$ (wobei Verschiebung, Drehung und Spiegelung erlaubt sind) ohne Überlappungen und ohne Lücken.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Veranschaulichung der ersten beiden Beispiel-Testfälle.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^3$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die erste Zeile enthält zwei ganze Zahlen $x_a$ und $y_a$ ($-100 \le x_a, y_a \le 100$), die Koordinaten von Punkt $A$.

Die zweite Zeile enthält zwei ganze Zahlen $x_b$ und $y_b$ ($-100 \le x_b, y_b \le 100$), die Koordinaten von Punkt $B$.

Die dritte Zeile enthält zwei ganze Zahlen $x_c$ und $y_c$ ($-100 \le x_c, y_c \le 100$), die Koordinaten von Punkt $C$.

Die vierte Zeile enthält zwei Brüche $x_{d1}/x_{d2}$ und $y_{d1}/y_{d2}$, wobei $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ ganze Zahlen sind, die $-10^7 < x_{d1}, y_{d1} < 10^7$ und $0 < x_{d2}, y_{d2} < 10^7$ erfüllen und die Koordinaten von Punkt $D$ darstellen.

Es ist garantiert, dass $A$, $B$ und $C$ ein nicht-entartetes Dreieck bilden.

Ausgabe

Geben Sie für jeden Testfall in einer Zeile "Yes" aus, wenn eine gültige Parkettierung existiert, sodass Punkt $D$ auf einer Kante oder einer Ecke von mindestens einem Dreieck im Muster liegt. Andernfalls geben Sie "No" aus.

Beispiele

Eingabe 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

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