Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

บนโต๊ะขนาดอนันต์ คุณได้รับจุดสองจุดที่แตกต่างกันคือ $A = (A_x, A_y)$ และ $B = (B_x, B_y)$

คุณยังมีกิ่งไม้ $M$ กิ่ง ซึ่งแต่ละกิ่งเป็นส่วนของเส้นตรงที่มีความยาว $W$ คุณสามารถวางกิ่งไม้เหล่านี้ที่ใดก็ได้บนโต๊ะ ด้วยตำแหน่งและทิศทางใดก็ได้ กิ่งไม้สามารถทับซ้อนกันได้ อย่างไรก็ตาม ต้องไม่มีกิ่งไม้ใดที่มีจุด $A$ หรือจุด $B$ อยู่ด้วย

มดตัวหนึ่งเริ่มต้นที่ $A$ และต้องการเดินไปยัง $B$ มันสามารถเดินไปที่ใดก็ได้บนโต๊ะ ยกเว้นว่ามันไม่สามารถเดินข้ามกิ่งไม้ใดๆ ได้

คุณต้องการวางกิ่งไม้เพื่อให้ความยาวของเส้นทางที่สั้นที่สุดสำหรับมดจาก $A$ ไปยัง $B$ มีค่ามากที่สุดเท่าที่จะเป็นไปได้

หากสามารถปิดกั้นมดได้อย่างสมบูรณ์จนไม่มีเส้นทางจาก $A$ ไปยัง $B$ คำตอบคือ $-1$

มิฉะนั้น ให้ $L$ เป็นค่าขอบเขตบนน้อยสุด (supremum)$^\dagger$ ของความยาวเส้นทางที่สั้นที่สุดจาก $A$ ไปยัง $B$ จากการจัดวางกิ่งไม้ที่ถูกต้องทั้งหมด หากมีการจัดวางที่ทำให้ได้ค่านี้ $L$ ก็คือค่าสูงสุด หากไม่มีการจัดวางเดี่ยวๆ ใดที่ทำได้ แต่สามารถเข้าใกล้ค่านี้ได้เรื่อยๆ คุณก็ยังต้องแสดงผลค่า $L$

$^\dagger$ ค่าขอบเขตบนน้อยสุด (supremum) ของเซตของจำนวนจริง คือจำนวนจริงที่ 작ที่สุดที่มีค่ามากกว่าหรือเท่ากับทุกค่าในเซตนั้น ซึ่งอาจจะมีหรือไม่มีค่าในเซตที่เท่ากับค่านี้ก็ได้

ข้อมูลนำเข้า

ข้อมูลนำเข้ามีรูปแบบดังต่อไปนี้:

T
A_x A_y B_x B_y M W
...
  • ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
  • $1 \le T \le 10^4$
  • $0 \le A_x, A_y, B_x, B_y \le 10^9$
  • $1 \le M, W \le 10^9$
  • รับประกันว่า $(A_x, A_y) \ne (B_x, B_y)$

ข้อมูลส่งออก

สำหรับแต่ละชุดทดสอบ:

  • พิมพ์ $-1$ หากสามารถปิดกั้นมดได้อย่างสมบูรณ์
  • มิฉะนั้น พิมพ์จำนวนจริงหนึ่งจำนวน — ค่า $L$ ที่นิยามไว้ข้างต้น

ให้ $X$ เป็นคำตอบที่ถูกต้องและ $Y$ เป็นผลลัพธ์ของคุณ ผลลัพธ์ของคุณจะถือว่าถูกต้องก็ต่อเมื่อ $|Y - X| \le 10^-6 \cdot \max(1, |X|)$

ตัวอย่าง

ข้อมูลนำเข้า 1

2
0 0 1 1 343 434
4 5 786331192 707731892 1 639711202

ข้อมูลส่งออก 1

-1
1425074478.231629371643066

หมายเหตุ

ชุดทดสอบที่ 1: สามารถแสดงให้เห็นได้ว่าด้วยการจัดวางกิ่งไม้อย่างเหมาะสมที่สุด จะสามารถปิดกั้นมดได้อย่างสมบูรณ์

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.