Universal Cup Judging System

Universal Cup

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

뛰어난 억만장자인 차이(Cai)는 매우 특별한 집착을 가지고 있습니다. 그는 자신의 발이 타일의 변이나 꼭짓점, 즉 어떤 바닥 타일의 경계선 위에 단단히 딛고 있을 때만 편안함을 느낍니다. 최근에 그는 동일한 최고급 삼각형 바닥 타일 컬렉션을구입했습니다. 그는 이 타일들을 사용하여 새 저택의 길고 곧은 복도에 타일을 깔 계획입니다.

복도는 2차원 평면 위의 무한한 띠 모양 영역입니다. 디자인이 자신의 최고 기준을 충족하도록 하기 위해 차이는 엄격한 타일 시공 규칙을 지시했습니다. 모든 삼각형 타일은 복도의 전체 폭을 가로질러 두 평행한 경계선에 모두 닿도록 배치되어야 합니다. 이는 띠 영역의 연속적인 단일 행 테셀레이션(쪽매맞춤)을 만듭니다. 이 타일들 중 하나는 그가 가장 좋아하는 기준 삼각형과 정확히 일치해야 하며, 다른 모든 타일은 그 삼각형과 합동이어야 합니다.

차이는 현재 복도의 고정된 위치에 서 있습니다. 그는 긴 하루 동안의 테라포밍 작업 끝에 지쳐 있으며, 솔직히 말해서 전혀 움직이지 않을 것입니다. 그는 결과 패턴이 자신의 규칙을 따르기만 한다면, 기준 삼각형에서 시작하여 타일들이 바닥 전체로 자동 확장되기를 원합니다. 물론 타일의 변이나 꼭짓점이 그의 현재 위치와 일치할 때만 성공입니다!

여러분의 작업은 차이의 현재 위치인 점 $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.