Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 2048 MB 満点: 100 難易度: [表示] ハック可能 ✓
統計

Cai, vị tỷ phú xuất chúng, có một nỗi ám ảnh rất đặc biệt: ông chỉ cảm thấy thoải mái khi đôi chân của mình đặt vững chắc trên một cạnh hoặc một đỉnh của lớp lát gạch — tức là trên biên của một viên gạch lát sàn nào đó. Gần đây, ông đã mua một bộ sưu tập các viên gạch lát sàn hình tam giác cao cấp giống hệt nhau. Ông dự định sử dụng những viên gạch này để lát một hành lang dài và thẳng trong dinh thự mới của mình.

Hành lang là một dải vô hạn trên mặt phẳng hai chiều. Để đảm bảo thiết kế đáp ứng các tiêu chuẩn tối cao của mình, Cai đã đưa ra một quy tắc lát gạch nghiêm ngặt: mỗi viên gạch hình tam giác phải được đặt sao cho nó trải rộng hết chiều ngang của hành lang, chạm vào cả hai đường biên song song. Điều này tạo ra một phép lát phẳng (tessellation) một hàng liên tục trên dải. Một trong những viên gạch này phải khớp chính xác với hình tam giác tham chiếu yêu thích của ông, và tất cả các viên gạch khác phải bằng (đồng dạng và cùng kích thước) với nó.

Cai hiện đang đứng tại một vị trí cố định trong hành lang. Ông đã kiệt sức sau một ngày dài làm việc cải tạo địa hình và thành thật mà nói, ông sẽ không di chuyển chút nào. Ông muốn những viên gạch tự động mở rộng khắp sàn nhà bắt đầu từ tam giác tham chiếu của mình, miễn là hoa văn thu được tuân theo quy tắc của ông. Tất nhiên, điều đó chỉ thành công nếu một cạnh hoặc đỉnh của các viên gạch trùng với vị trí hiện tại của ông!

Nhiệm vụ của bạn là xác định xem liệu có thể lát hành lang sao cho vị trí hiện tại của Cai, điểm $D$, nằm chính xác trên một cạnh hoặc một đỉnh của phép lát phẳng chứa $\triangle ABC$ hay không. Biên của hành lang được định nghĩa là hai đường thẳng song song duy nhất $l_1$ và $l_2$ sao cho $l_1$ đi qua $A$ và $B$, còn $l_2$ đi qua $C$. Một phép lát phẳng của dải tạo bởi $(l_1, l_2)$ là cách lát toàn bộ dải bằng các bản sao bằng nhau của tam giác $\triangle ABC$ (cho phép tịnh tiến, xoay và đối xứng), không chồng lấn và không có khe hở.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Minh họa cho hai bộ dữ liệu ví dụ đầu tiên.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^3$) cho biết số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $x_a$ và $y_a$ ($-100 \le x_a, y_a \le 100$), tọa độ của điểm $A$.

Dòng thứ hai chứa hai số nguyên $x_b$ và $y_b$ ($-100 \le x_b, y_b \le 100$), tọa độ của điểm $B$.

Dòng thứ ba chứa hai số nguyên $x_c$ và $y_c$ ($-100 \le x_c, y_c \le 100$), tọa độ của điểm $C$.

Dòng thứ tư chứa hai phân số $x_{d1}/x_{d2}$ và $y_{d1}/y_{d2}$, trong đó $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ là các số nguyên thỏa mãn $-10^7 < x_{d1}, y_{d1} < 10^7$ và $0 < x_{d2}, y_{d2} < 10^7$, biểu thị tọa độ của điểm $D$.

Dữ liệu đảm bảo rằng $A$, $B$ và $C$ tạo thành một tam giác không suy biến.

Kết quả

Đối với mỗi bộ dữ liệu, in ra "Yes" trên một dòng nếu tồn tại một phép lát phẳng hợp lệ sao cho điểm $D$ nằm trên một cạnh hoặc một đỉnh của ít nhất một hình tam giác trong mẫu lát. Ngược lại, in ra "No".

Ví dụ

Dữ liệu vào 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

Kết quả 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.