Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 2048 MB 总分: 100 难度: [显示] 可 Hack ✓
统计

Cai, sang miliarder luar biasa, memiliki obsesi yang sangat khusus: ia hanya merasa nyaman ketika kakinya berpijak dengan kokoh pada sisi atau titik sudut ubin — yaitu, pada batas dari suatu ubin lantai. Baru-baru ini, ia memperoleh koleksi ubin lantai segitiga mewah yang identik. Ia berencana menggunakan ubin-ubin ini untuk memasang ubin di koridor panjang yang lurus di rumah mewah barunya.

Koridor tersebut adalah sebuah pita tak hingga pada bidang dua dimensi. Untuk memastikan desainnya memenuhi standar tertingginya, Cai telah menetapkan aturan pemasangan ubin yang ketat: setiap ubin segitiga harus ditempatkan sedemikian rupa sehingga membentang selebar koridor, menyentuh kedua garis batas yang sejajar. Hal ini menciptakan teselasi (pengubinan) satu baris yang kontinu pada pita tersebut. Salah satu ubin ini harus tepat cocok dengan segitiga referensi favoritnya, dan semua ubin lainnya harus kongruen dengannya.

Cai saat ini berdiri di lokasi tetap di lorong tersebut. Ia sangat lelah setelah seharian bekerja melakukan teraformasi dan,terus terang, tidak akan bergerak sama sekali. Ia ingin ubin-ubin tersebut tumbuh secara otomatis di seluruh lantai mulai dari segitiga referensinya, selama pola yang dihasilkan mengikuti aturannya. Tentu saja, hal itu hanya dianggap berhasil jika sisi atau titik sudut ubin berimpit dengan posisinya saat ini!

Tugas Anda adalah menentukan apakah mungkin memasang ubin di koridor sedemikian rupa sehingga posisi Cai saat ini, titik $D$, terletak tepat pada sisi atau titik sudut dari teselasi yang memuat $\triangle ABC$. Batas-batas koridor didefinisikan sebagai dua garis sejajar unik $l_1$ dan $l_2$ sedemikian sehingga $l_1$ melewati $A$ dan $B$, serta $l_2$ melewati $C$. Suatu teselasi dari pita yang dibentuk oleh $(l_1, l_2)$ adalah pengubinan seluruh pita menggunakan salinan kongruen dari segitiga $\triangle ABC$ (mengizinkan translasi, rotasi, dan refleksi), tanpa tumpang tindih dan tanpa celah.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Ilustrasi dari dua kasus uji contoh pertama.

Masukan

Terdapat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^3$) yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat $x_a$ dan $y_a$ ($-100 \le x_a, y_a \le 100$), koordinat titik $A$.

Baris kedua berisi dua bilangan bulat $x_b$ dan $y_b$ ($-100 \le x_b, y_b \le 100$), koordinat titik $B$.

Baris ketiga berisi dua bilangan bulat $x_c$ dan $y_c$ ($-100 \le x_c, y_c \le 100$), koordinat titik $C$.

Baris keempat berisi dua pecahan $x_{d1}/x_{d2}$ dan $y_{d1}/y_{d2}$, di mana $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ adalah bilangan bulat yang memenuhi $-10^7 < x_{d1}, y_{d1} < 10^7$ dan $0 < x_{d2}, y_{d2} < 10^7$, yang menyatakan koordinat titik $D$.

Dijamin bahwa $A$, $B$, dan $C$ membentuk segitiga tak-degenerat.

Keluaran

Untuk setiap kasus uji, keluarkan "Yes" dalam satu baris jika terdapat teselasi yang valid sedemikian sehingga titik $D$ terletak pada sisi atau titik sudut dari setidaknya satu segitiga dalam pola tersebut. Jika tidak, keluarkan "No".

Contoh

Masukan 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

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