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

傑出的億萬富翁蔡先生有一個非常特別的強迫症:只有當他的雙腳牢牢地踩在瓷磚的邊或頂點上(即某塊地板磚的邊界上)時,他才會感到舒適。最近,他購入了一批相同的、高檔的三角形地板磚。他計畫用這些瓷磚在他新豪宅的一條長而直的走廊上鋪設地板。

走廊是二維平面上的一個無限帶狀區域。為了確保設計符合他的最高標準,蔡先生制定了嚴格的鋪設規則:每塊三角形瓷磚的放置必須跨越走廊的整個寬度,並同時接觸兩條平行的邊界線。這將在帶狀區域上形成一個連續的、單排的鑲嵌圖案。其中一塊瓷磚必須與他最喜歡的參考三角形完全一致,而所有其他瓷磚必須與該參考三角形全等。

蔡先生目前正站在走廊裡的一個固定位置。在經歷了一整天漫長的改造工作後,他已經精疲力竭,坦白地說,他根本不想動。他希望瓷磚能從他的參考三角形開始,自動在地面上向外延伸鋪設,只要最終的圖案符合他的規則即可。當然,只有當瓷磚的某條邊或某個頂點與他當前的位置重合時,才算成功!

你的任務是確定是否可能鋪設走廊,使得蔡先生當前的位置(點 $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$ 構成一個非退化的三角形。

輸出格式

對於每組測試資料,如果存在一種合法的鋪設方案,使得點 $D$ 恰好落在圖案中至少一個三角形的邊或頂點上,則在一行中輸出 "Yes"。否則,輸出 "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.