على طاولة غير محدودة، تُعطى نقطتين مختلفتين $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: يمكن إثبات أنه من خلال وضع العصي بشكل مثالي، يمكن محاصرة النملة بالكامل.