Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 2048 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

Көрнекті миллиардер Цайдың өте ерекше әдеті бар: ол табаны плитканың қабырғасына немесе төбесіне — яғни қандай да бір еден плиткасының шекарасына — нық тиіп тұрғанда ғана өзін жайлы сезінеді. Жақында ол бірдей, жоғары сапалы үшбұрышты еден плиткаларының топтамасын сатып алды. Ол осы плиткаларды жаңа зәулім үйіндегі ұзын әрі түзу дәлізге төсеуді жоспарлап отыр.

Дәліз — екі өлшемді жазықтықтағы шексіз жолақ. Дизайн оның ең жоғары стандарттарына сай болуы үшін Цай қатаң төсеу ережесін белгіледі: әрбір үшбұрышты плитка дәліздің бүкіл енін қамтитындай және параллель екі шекара сызығына да тиіп тұратындай етіп орналастырылуы керек. Бұл жолақтың үздіксіз, бір қатарлы мозаикасын (тесселяциясын) құрайды. Осы плиткалардың бірі оның сүйікті эталондық үшбұрышымен дәл сәйкес келуі керек, ал қалған барлық плиткалар оған конгруэнтті (тең) болуы тиіс.

Цай қазір дәліздегі бекітілген бір орында тұр. Ол ұзақ күнге созылған терраформациялау жұмыстарынан кейін қатты шаршады және, шынын айтқанда, орнынан мүлдем қозғалмайды. Ол алынған өрнек оның ережелеріне бағынатын болса, плиткалардың эталондық үшбұрыштан бастап еден бойымен автоматты түрде жайылып төселгенін қалайды. Әрине, плиткалардың қабырғасы немесе төбесі оның қазіргі тұрған орнымен сәйкес келсе ғана бұл сәтті болып есептеледі!

Сіздің міндетіңіз — Цайдың қазіргі орны, яғни $D$ нүктесі, $\triangle ABC$ үшбұрышын қамтитын мозаиканың қабырғасында немесе төбесінде дәл жататындай етіп дәлізге плитка төсеу мүмкін бе, соны анықтау. Дәліздің шекаралары $l_1$ түзуі $A$ мен $B$ арқылы өтетін, ал $l_2$ түзуі $C$ арқылы өтетін бірегей екі параллель $l_1$ және $l_2$ түзулері ретінде анықталады. $(l_1, l_2)$ арқылы құрылған жолақтың мозаикасы дегеніміз — бүкіл жолақты $\triangle ABC$ үшбұрышының конгруэнтті көшірмелерін (параллель көшіруге, бұруға және шағылыстыруға рұқсат етіледі) пайдаланып, ешқандай беттесусіз және саңылаусыз төсеп шығу.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Алғашқы екі мысал тест жағдайының иллюстрациясы.

Кіріс деректер

Бірнеше тест жиынтығы берілген. Кіріс деректердің бірінші жолында тест жиынтықтарының санын білдіретін бүтін сан $T$ ($1 \le T \le 10^3$) берілген. Әрбір тест жиынтығы үшін:

Бірінші жолда $A$ нүктесінің координаттарын білдіретін екі бүтін сан $x_a$ және $y_a$ ($-100 \le x_a, y_a \le 100$) берілген.

Екінші жолда $B$ нүктесінің координаттарын білдіретін екі бүтін сан $x_b$ және $y_b$ ($-100 \le x_b, y_b \le 100$) берілген.

Үшінші жолда $C$ нүктесінің координаттарын білдіретін екі бүтін сан $x_c$ және $y_c$ ($-100 \le x_c, y_c \le 100$) берілген.

Төртінші жолда $D$ нүктесінің координаттарын білдіретін екі бөлшек $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$ нүктелері азғындалмаған үшбұрыш құрайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиынтығы үшін, егер өрнектегі кемінде бір үшбұрыштың қабырғасында немесе төбесінде $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.