Universal Cup Judging System

Universal Cup

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

Видатний мільярдер Цай має дуже специфічну одержимість: він почувається комфортно лише тоді, коли його ступні твердо стоять на стороні або вершині замощення — тобто на межі деякої підлогової плитки. Нещодавно він придбав колекцію однакових елітних трикутних підлогових плиток. Він планує використати ці плитки, щоб викласти підлогу в довгому прямому коридорі свого нового маєтку.

Коридор є нескінченною смугою на двовимірній площині. Щоб дизайн відповідав його найвищим стандартам, Цай встановив суворе правило укладання: кожна трикутна плитка повинна розміщуватися так, щоб перекривати всю ширину коридору, торкаючись обох паралельних межових прямих. Це створює неперервне однорядне замощення (теселяцію) смуги. Одна з цих плиток повинна точно збігатися з його улюбленим еталонним трикутником, а всі інші плитки мають бути конгруентними йому.

Зараз Цай стоїть у фіксованій точці коридору. Він виснажений після довгого дня робіт із тераформування і, відверто кажучи, взагалі не збирається рухатися з місця. Він хоче, щоб плитки автоматично розрослися по підлозі, починаючи від його еталонного трикутника, за умови, що підсумковий візерунок відповідатиме його правилам. Звісно, успіхом вважається лише той випадок, коли сторона або вершина плиток збіжиться з його поточним положенням!

Ваше завдання — визначити, чи можна викласти коридор плиткою так, щоб поточне положення Цая, точка $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.