Universal Cup Judging System

Universal Cup

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

傑出嘅億萬富翁蔡先生有一個非常特別嘅強迫症:只有當佢對腳牢牢咁踩喺階磚嘅邊或者頂點上面(即係某塊地板磚嘅邊界上面)時,佢先至會覺得舒服。最近,佢買入咗一批相同嘅、高檔嘅三角形地板磚。佢計劃用呢啲階磚喺佢新豪宅嘅一條長而直嘅走廊度鋪設地板。

走廊係二維平面上面嘅一個無限帶狀區域。為咗確保設計符合佢嘅最高標準,蔡先生制定咗嚴格嘅鋪設規則:每塊三角形階磚嘅擺放必須跨越走廊嘅成個闊度,並同時接觸兩條平行嘅邊界線。呢個會喺帶狀區域上面形成一個連續嘅、單排嘅鑲嵌圖案。其中一塊階磚必須同佢最鍾意嘅參考三角形完全一致,而所有其他階磚必須同該參考三角形全等。

蔡先生目前企喺走廊入面嘅一個固定位置。喺經歷咗成日漫長嘅改造工作之後,佢已經精疲力竭,坦白講,佢根本唔想郁。佢希望階磚可以由佢嘅參考三角形開始,自動喺地面上向外延伸鋪設,只要最終嘅圖案符合佢嘅規則就得。當然,只有當階磚嘅某條邊或者某個頂點同佢當前嘅位置重合時,先至算成功!

你嘅任務係確定係咪可能鋪設走廊,令到蔡先生當前嘅位置(點 $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.