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.