Á óendanlegu borði eru gefnir tveir ólíkir punktar $A = (A_x, A_y)$ og $B = (B_x, B_y)$.
Þú ert líka með $M$ prik, þar sem hvert prik er strik af lengd $W$. Þú mátt setja þessi prik hvar sem er á borðið, í hvaða stöðu og stefnu sem er. Prikin mega skarast. Hins vegar má ekkert prik innihalda punktinn $A$ eða punktinn $B$.
Maur byrjar í $A$ og vill komast í $B$. Hann má ganga hvar sem er á borðinu, nema hvað hann getur ekki farið yfir neitt prik.
Þú vilt raða prikunum þannig að lengd stystu leiðar maursins frá $A$ til $B$ verði eins mikil og mögulegt er.
Ef hægt er að loka alveg fyrir maurinn þannig að engin leið sé til frá $A$ til $B$, þá er svarið $-1$.
Annars látum við $L$ vera efra mark (supremum)$^\dagger$ lengda stystu leiða frá $A$ til $B$ yfir allar gildar uppsetningar á prikunum. Ef til er uppsetning sem nær þessu gildi, þá er $L$ einfaldlega hámarkið. Ef engin einstök uppsetning nær því, en uppsetningar geta komist eins nálægt því og vera vill, verður þú samt að prenta $L$.
$^\dagger$ Efra mark (minnsta יfirmark) mengis rauntalna er minnsta rauntalan sem er stærri en eða jöfn hverju gildi í menginu. Það getur annaðhvort náðst af gildi í menginu eða ekki.
Inntak
Inntakið er gefið á eftirfarandi sniði:
T A_x A_y B_x B_y M W ...
- Öll inntaksgildi eru heiltölur.
- $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ð er tryggt að $(A_x, A_y) \ne (B_x, B_y)$.
Úttak
Fyrir hvert prófunartilvik:
- Prentaðu $-1$ ef hægt er að loka alveg fyrir maurinn;
- Annars skaltu prenta eina rauntölu — gildið $L$ sem skilgreint er hér að ofan.
Látum $X$ vera rétta svarið og $Y$ vera úttakið þitt. Úttakið þitt telst rétt ef og aðeins ef $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.
Dæmi
Inntak 1
2 0 0 1 1 343 434 4 5 786331192 707731892 1 639711202
Úttak 1
-1 1425074478.231629371643066
Athugasemd
Prófunartilvik 1: Hægt er að sýna fram á að með því að raða prikunum á besta hátt má loka alveg fyrir maurinn.