Шексіз үстел бетінде екі түрлі $A = (A_x, A_y)$ және $B = (B_x, B_y)$ нүктелері берілген.
Сондай-ақ сізде әрқайсысының ұзындығы $W$ болатын кесінді түріндегі $M$ таяқша бар. Бұл таяқшаларды үстелдің кез келген жеріне, кез келген орын мен бағытта орналастыруға болады. Таяқшалар бірінің үстіне бірі түсуі мүмкін. Алайда, ешбір таяқша $A$ нүктесін немесе $B$ нүктесін қамтымауы тиіс.
Құмырсқа $A$ нүктесінен шығып, $B$ нүктесіне жеткісі келеді. Ол үстелдің кез келген жерімен жүре алады, бірақ ешбір таяқшаны кесіп өте алмайды.
Сіз құмырсқаның $A$-дан $B$-ға дейінгі ең қысқа жолының ұзындығы мүмкіндігінше үлкен болатындай етіп таяқшаларды орналастырғыңыз келеді.
Егер құмырсқаны толығымен бөгеп, $A$-дан $B$-ға баратын жол мүлдем болмайтындай ету мүмкін болса, жауап $-1$ болады.
Әйтпесе, $L$ — таяқшаларды барлық дұрыс орналастырулар бойынша $A$-дан $B$-ға дейінгі ең қысқа жол ұзындықтарының супремумы$^\dagger$ болсын. Егер осы мәнге жететін орналастыру бар болса, $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-тест жағдайы: Таяқшаларды тиімді орналастыру арқылы құмырсқаны толығымен бөгеуге болатынын көрсетуге болады.