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 มหาเศรษฐีผู้โดดเด่น มีความหลงใหลที่เฉพาะเจาะจงมาก: เขาจะรู้สึกสบายใจก็ต่อเมื่อเท้าของเขาวางอยู่บนขอบหรือจุดยอดของการปูกระเบื้องอย่างมั่นคง — นั่นคืออยู่บนเส้นขอบของกระเบื้องปูพื้นแผ่นใดแผ่นหนึ่ง เมื่อไม่นานมานี้ เขาได้ซื้อคอลเลกชันกระเบื้องปูพื้นรูปสามเหลี่ยมระดับไฮเอนด์ที่เหมือนกันทุกประการ เขาวางแผนที่จะใช้กระเบื้องเหล่านี้ปูทางเดินที่ยาวและตรงในคฤหาสน์หลังใหม่ของเขา

ทางเดินนี้เป็นแถบอนันต์บนระนาบสองมิติ เพื่อให้มั่นใจว่าการออกแบบเป็นไปตามมาตรฐานสูงสุดของเขา Cai ได้กำหนดกฎการปูกระเบื้องที่เข้มงวด: กระเบื้องรูปสามเหลี่ยมทุกแผ่นจะต้องวางให้พาดผ่านความกว้างทั้งหมดของทางเดิน โดยสัมผัสกับเส้นขอบที่ขนานกันทั้งสองเส้น สิ่งนี้จะสร้าง เทสเซลเลชัน (tessellation) แถวเดียวที่ต่อเนื่องกันของแถบ กระเบื้องแผ่นหนึ่งจะต้องตรงกับรูปสามเหลี่ยมอ้างอิงที่เขาชื่นชอบทุกประการ และกระเบื้องแผ่นอื่นๆ ทั้งหมดจะต้องเท่ากันทุกประการกับรูปสามเหลี่ยมนั้น

ปัจจุบัน Cai ยืนอยู่ที่ตำแหน่งคงที่ในโถงทางเดิน เขาเหนื่อยล้าหลังจากทำงานปรับสภาพพื้นผิวโลกมาทั้งวัน และพูดตามตรงคือเขาจะไม่ขยับไปไหนเลย เขาต้องการให้กระเบื้องขยายตัวออกไปทั่วพื้นโดยอัตโนมัติโดยเริ่มจากรูปสามเหลี่ยมอ้างอิงของเขา ตราบใดที่ลวดลายที่ได้เป็นไปตามกฎของเขา แน่นอนว่ามันจะสำเร็จก็ต่อเมื่อขอบหรือจุดยอดของกระเบื้องตรงกับตำแหน่งปัจจุบันของเขาพอดี!

งานของคุณคือพิจารณาว่าเป็นไปได้หรือไม่ที่จะปูกระเบื้องทางเดิน بحيث ตำแหน่งปัจจุบันของ Cai คือจุด $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.