על שולחן אינסופי נתונות שתי נקודות שונות $A = (A_x, A_y)$ ו-$B = (B_x, B_y)$.
יש לך גם $M$ מקלות, שכל אחד מהם הוא קטע ישר באורך $W$. באפשרותך להניח את המקלות הללו בכל מקום על השולחן, בכל מיקום ובכל כיוון. המקלות רשאים לחפוף. עם זאת, אף מקל אינו יכול להכיל את הנקודה $A$ או את הנקודה $B$.
נמלה מתחילה ב-$A$ ורוצה להגיע אל $B$. היא יכולה ללכת בכל מקום על השולחן, פרט לכך שאינה יכולה לחצות אף מקל.
ברצונך להניח את המקלות כך שאורך המסלול הקצר ביותר עבור הנמלה מ-$A$ אל $B$ יהיה גדול ככל האפשר.
אם ניתן לחסום את הנמלה לחלוטין כך שלא קיים מסלול מ-$A$ אל $B$, התשובה היא $-1$.
אחרת, יהי $L$ הסופרמום$^\dagger$ של אורכי המסלולים הקצרים ביותר מ-$A$ אל $B$ על פני כל ההנחות החוקיות של המקלות. אם קיימת הנחה שמשיגה ערך זה, $L$ הוא פשוט המקסימום. אם אף הנחה בודדת אינה משיגה אותו, אך הנחות יכולות להתקרב אליו כרצוננו, עדיין עליך להדפיס את $L$.
$^\dagger$ הסופרמום (החסם העליון הקטן ביותר) של קבוצת מספרים ממשיים הוא המספר הממשי הקטן ביותר שגדול או שווה לכל ערך בקבוצה. הוא עשוי להתקבל או שלא להתקבל על ידי ערך בקבוצה.
קלט
הקלט ניתן בפורמט הבא:
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: ניתן להראות שעל ידי הנחת המקלות באופן אופטימלי, ניתן לחסום את הנמלה לחלוטין.