Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 2048 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

傑出した大富豪である蔡(Cai)氏は、非常に独特なこだわりを持っています。彼は、タイルの辺または頂点——すなわち、床タイルの境界線上——にしっかりと両足を置いているときにしか安心できないのです。最近、彼は高級で同一の三角形の床タイルを大量に手に入れました。彼はこれらのタイルを使って、新しい豪邸の長く真っ直ぐな廊下にタイルを敷き詰める計画を立てています。

廊下は 2 次元平面上の無限の帯状領域です。デザインが彼の最高基準を満たすように、蔡氏は厳格な敷き詰め規則を定めました。すべての三角形のタイルは、廊下の幅全体にまたがり、2 本の平行な境界線の両方に接するように配置しなければなりません。これにより、帯状領域の連続した 1 列の平面充填(テッセレーション)が作られます。これらのタイルのうちの 1 つは彼のお気に入りの基準三角形と完全に一致しなければならず、他のすべてのタイルはそれと合同でなければなりません。

蔡氏は現在、廊下の固定された位置に立っています。丸一日の長いテラフォーミング作業の後に疲れ果てており、率直に言って一歩も動きたくありません。彼は、結果として得られるパターンが彼の規則に従う限り、基準三角形から始まって床全体にタイルが自動的に広がっていくことを望んでいます。もちろん、タイルの辺または頂点が彼の現在位置と一致した場合にのみ成功となります!

あなたの仕事は、蔡氏の現在位置である点 $D$ が、$\triangle ABC$ を含む平面充填の辺または頂点上にちょうど乗るように廊下にタイルを敷き詰めることが可能かどうかを判定することです。廊下の境界は、$l_1$ が $A$ と $B$ を通り、$l_2$ が $C$ を通るような一意な 2 本の平行線 $l_1$ と $l_2$ として定義されます。$(l_1, l_2)$ によって形成される帯状領域の平面充填とは、三角形 $\triangle ABC$ の合同なコピー(平行移動、回転、鏡映を許す)を用いて、重なりも隙間もなく帯状領域全体を敷き詰めることです。

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

最初の 2 つのサンプルテストケースの図解。

入力

複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す整数 $T$ ($1 \le T \le 10^3$) が与えられます。各テストケースについて:

1 行目には、点 $A$ の座標を表す 2 つの整数 $x_a$ と $y_a$ ($-100 \le x_a, y_a \le 100$) が与えられます。

2 行目には、点 $B$ の座標を表す 2 つの整数 $x_b$ と $y_b$ ($-100 \le x_b, y_b \le 100$) が与えられます。

3 行目には、点 $C$ の座標を表す 2 つの整数 $x_c$ と $y_c$ ($-100 \le x_c, y_c \le 100$) が与えられます。

4 行目には、点 $D$ の座標を表す 2 つの分数 $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$ を満たす整数です。

$A$, $B$, $C$ が非退化な三角形をなすことが保証されています。

出力

各テストケースについて、パターン内の少なくとも 1 つの三角形の辺または頂点上に点 $D$ が乗るような有効な平面充填が存在する場合は "Yes" を、そうでない場合は "No" を 1 行に出力してください。

入出力例

入力例 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.