บนโต๊ะขนาดอนันต์ คุณได้รับจุดสองจุดที่แตกต่างกันคือ $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: สามารถแสดงให้เห็นได้ว่าด้วยการจัดวางกิ่งไม้อย่างเหมาะสมที่สุด จะสามารถปิดกั้นมดได้อย่างสมบูรณ์