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

Cai, l'éminent milliardaire, a une obsession très particulière : il ne se sent à l'aise que lorsque ses pieds sont fermement posés sur une arête ou un sommet du pavage — c'est-à-dire sur le bord d'un carreau de sol. Récemment, il a acquis une collection de carreaux de sol triangulaires haut de gamme identiques. Il prévoit d'utiliser ces carreaux pour carreler un long couloir rectiligne dans son nouveau manoir.

Le couloir est une bande infinie sur un plan bidimensionnel. Pour s'assurer que le design réponde à ses normes suprêmes, Cai a imposé une règle de pavage stricte : chaque carreau triangulaire doit être placé de manière à couvrir toute la largeur du couloir, en touchant les deux lignes de frontière parallèles. Cela crée un pavage (tessellation) continu sur une seule rangée de la bande. L'un de ces carreaux doit correspondre exactement à son triangle de référence préféré, et tous les autres carreaux doivent lui être congruents.

Cai se tient actuellement à un endroit fixe dans le couloir. Il est épuisé après une longue journée de travaux de terraformation et, bien franchement, ne bougera pas du tout. Il veut que les carreaux se déploient automatiquement sur le sol à partir de son triangle de référence, tant que le motif résultant respecte ses règles. Bien sûr, ce n'est une réussite que si une arête ou un sommet des carreaux coïncide avec sa position actuelle !

Votre tâche consiste à déterminer s'il est possible de carreler le couloir de telle sorte que la position actuelle de Cai, le point $D$, se trouve exactement sur une arête ou un sommet du pavage contenant $\triangle ABC$. Les frontières du couloir sont définies comme les deux uniques droites parallèles $l_1$ et $l_2$ telles que $l_1$ passe par $A$ et $B$, et $l_2$ passe par $C$. Un pavage de la bande formée par $(l_1, l_2)$ est un recouvrement de toute la bande à l'aide de copies congruentes du triangle $\triangle ABC$ (en autorisant les translations, les rotations et les réflexions), sans chevauchements ni espaces vides.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Illustration des deux premiers cas de test de l'exemple.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^3$) indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient deux entiers $x_a$ et $y_a$ ($-100 \le x_a, y_a \le 100$), les coordonnées du point $A$.

La deuxième ligne contient deux entiers $x_b$ et $y_b$ ($-100 \le x_b, y_b \le 100$), les coordonnées du point $B$.

La troisième ligne contient deux entiers $x_c$ et $y_c$ ($-100 \le x_c, y_c \le 100$), les coordonnées du point $C$.

La quatrième ligne contient deux fractions $x_{d1}/x_{d2}$ et $y_{d1}/y_{d2}$, où $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ sont des entiers satisfaisant $-10^7 < x_{d1}, y_{d1} < 10^7$ et $0 < x_{d2}, y_{d2} < 10^7$, représentant les coordonnées du point $D$.

Il est garanti que $A$, $B$ et $C$ forment un triangle non dégénéré.

Sortie

Pour chaque cas de test, affichez "Yes" sur une ligne s'il existe un pavage valide tel que le point $D$ se trouve sur une arête ou un sommet d'au moins un triangle du motif. Sinon, affichez "No".

Exemples

Entrée 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

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