Äärettömällä pöydällä on annettu kaksi eri pistettä $A = (A_x, A_y)$ ja $B = (B_x, B_y)$.
Sinulla on myös $M$ tikkua, joista jokainen on pituudeltaan $W$ oleva jana. Voit asettaa nämä tikut mihin tahansa pöydälle, mihin tahansa paikkaan ja asentoon. Tikut saavat mennä päällekkäin. Mikään tikku ei kuitenkaan saa sisältää pistettä $A$ tai pistettä $B$.
Muurahainen lähtee pisteestä $A$ ja haluaa päästä pisteeseen $B$. Se voi kävellä missä tahansa pöydällä, paitsi että se ei voi ylittää yhtäkään tikkua.
Haluat asettaa tikut niin, että muurahaisen lyhimmän reitin pituus pisteestä $A$ pisteeseen $B$ on mahdollisimman suuri.
Jos muurahaisen kulku on mahdollista estää kokonaan niin, ettei reittiä pisteestä $A$ pisteeseen $B$ ole olemassa, vastaus on $-1$.
Muussa tapauksessa olkoon $L$ pisteestä $A$ pisteeseen $B$ kulkevien lyhimpien reittien pituuksien supremum$^\dagger$ kaikkien kelvollisten tikkujen asettelujen yli. Jos on olemassa asettelu, jolla tämä arvo saavutetaan, $L$ on yksinkertaisesti maksimi. Jos mikään yksittäinen asettelu ei saavuta sitä, mutta asetteluilla voidaan päästä mielivaltaisen lähelle sitä, sinun on silti tulostettava $L$.
$^\dagger$ Reaalilukujoukon supremum (pienin yläraja) on pienin reaaliluku, joka on suurempi tai yhtä suuri kuin jokainen joukon alkio. Joukon alkio voi saavuttaa sen tai sitten ei.
Syöte
Syöte annetaan seuraavassa muodossa:
T A_x A_y B_x B_y M W ...
- Kaikki syötearvot ovatkokonaislukuja.
- $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$
- On taattu, että $(A_x, A_y) \ne (B_x, B_y)$.
Tuloste
Jokaista testitapausta kohden:
- Tulosta $-1$, jos muurahaisen kulku voidaan estää kokonaan;
- Muussa tapauksessa tulosta yksi reaaliluku — yllä määritelty arvo $L$.
Olkoon $X$ oikea vastaus ja $Y$ tulosteesi. Tulosteesi katsotaan oikeaksi jos ja vain jos $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.
Esimerkki
Syöte 1
2 0 0 1 1 343 434 4 5 786331192 707731892 1 639711202
Tuloste 1
-1 1425074478.231629371643066
Huomautus
Testitapaus 1: Voidaan osoittaa, että asettelemalla tikut optimaalisesti muurahaisen kulku voidaan estää kokonaan.