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), המיליארדר יוצא הדופן, יש אובססיה ייחודית מאוד: הוא מרגיש בנוח רק כאשר כפות רגליו נטועות היטב על צלע או קודקוד של הריצוף — כלומר, על השפה של אריח רצפה כלשהו. לאחרונה הוא רכש אוסף של אריחי רצפה משולשים יוקרתיים וזהים. הוא מתכנן להשתמש באריחים אלה כדי לרצף מסדרון ארוך וישר באחוזתו החדשה.

המסדרון הוא רצועה אינסופית במישור דו-ממדי. כדי להבטיח שהעיצוב יעמוד בסטנדרטים העليונים שלו, קאי הכתיב כלל ריצוף נוקשה: כל אריח משולש חייב להיות מונח כך שהוא חוצה את מלוא רוחבו של המסדרון, ונוגע בשני קווי הגבול המקבילים. זה יוצר ריצוף (טסלציה) רציף בשורה אחת של הרצועה. אחד האריחים הללו חייב להתאים בדיוק למשולש הייחוס האהוב עליו, וכל שאר האריחים חייבים להיות חופפים לו.

קאי עומד כעת במיקום קבוע במסדרון. הוא מותש לאחר יום ארוך של עבודות הארצה (terraforming) ובכנות, הוא לא יזוז כלל. הוא רוצה שהאריחים יתפשטו באופן אוטומטי על פני הרצפה החל ממשולש הייחוס שלו, כל עוד הדפוס המתקבל מציית לכללים שלו. כמובן, זוהי הצלחה רק אם צלע או קודקוד של האריחים מתלכדים עם מיקומו הנוכחי!

המשימה שלכם היא לקבוע האם ניתן לרצף את המסדרון כך שמיקומו הנוכחי של קאי, נקודה $D$, יימצא בדיוק על צלע או קודקוד של הריצוף המכיל את $\triangle ABC$. גבולות המסדרון מוגדרים כשני הישרים המקבילים היחידים $l_1$ ו-$l_2$ כך ש-$l_1$ עובר דרך $A$ ו-$B$, ו-$l_2$ עובר דרך $C$. ריצוף של הרצועה הנוצרת על ידי $(l_1, l_2)$ הוא כיסוי של הרצועה כולה באמצעות עותקים חופפים של המשולש $\triangle ABC$ (תוך מתן אפשרות להזזה, סיבוב ושיקוף), ללא חפיפות וללא רווחים.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

המחשה של שני מקרי הבדיקה הראשונים בדוגמה.

קלט

ישנם מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם $T$ ($1 \le T \le 10^3$) המציין את מספר מקרי הבדיקה. עבור כל מקרה בדיקה:

השורה הראשונה מכילה שני מספרים שלמים $x_a$ ו-$y_a$ ($-100 \le x_a, y_a \le 100$), הקואורדינטות של נקודה $A$.

השורה השנייה מכילה שני מספרים שלמים $x_b$ ו-$y_b$ ($-100 \le x_b, y_b \le 100$), הקואורדינטות של נקודה $B$.

השורה השלישית מכילה שני מספרים שלמים $x_c$ ו-$y_c$ ($-100 \le x_c, y_c \le 100$), הקואורדינטות של נקודה $C$.

השורה הרביעית מכילה שני שברים $x_{d1}/x_{d2}$ ו-$y_{d1}/y_{d2}$, כאשר $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ הם מספרים שלמים המקיימים $-10^7 < x_{d1}, y_{d1} < 10^7$ ו-$0 < x_{d2}, y_{d2} < 10^7$, המייצגים את הקואורדינטות של נקודה $D$.

מובטח ש-$A$, $B$ ו-$C$ יוצרים משולש לא מנוון.

פלט

עבור כל מקרה בדיקה, הדפיסו "Yes" בשורה אם קיים ריצוף חוקי כך שהנקודה $D$ נמצאת על צלע או קודקוד של לפחות משולש אחד בדפוס. אחרת, הדפיסו "No".

דוגמאות

קלט 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

פלט 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.