Charlie May böcəyi
Charlie uçmağı bacarır. Lakin bir nöqtədən digərinə keçmək onun üçün yorucu bir işdir. Əsas səbəb isə Charlie'nin bir may böcəyi olmasıdır. Bildiyimiz kimi, may böcəkləri (tarakanlarla qarışdırmayın) yöndəmsiz və yavaşdırlar. Onlar düz xətt boyunca uçmaq üçün müəyyən vaxta ehtiyac duyurlar və dönmələr üçün daha çox vaxt sərf edirlər. Bu məhdudiyyətləri nəzərə alaraq, Charlienin ən sürətli marşrutunu tapmasına kömək edə bilərsinizmi?
Giriş verilənləri
Giriş bir neçə instansiyadan ibarətdir. Hər bir instansiyanın ilk sətri N, S və T (1 ≤ N ≤ 1000, 1 ≤ S, T ≤ 1000) tam ədədlərini ehtiva edir. Burada N düz may böcəyi uçuş trayektoriyalarının (həmçinin "cockridorlar" kimi tanınır) sayını, S Charlienin saniyədə metrlə sürətini və T onun saniyədə dərəcə ilə dönmə sürətini göstərir. İkinci sətir başlanğıc nöqtəsini (X_f, Y_f, Z_f) və təyinat nöqtəsini (X_t, Y_t, Z_t) göstərən altı tam ədəd (0 ≤ X_f, Y_f, Z_f, X_t, Y_t, Z_t ≤ 10000) ehtiva edir.
Növbəti N sətirin hər biri 0 ≤ X_1, Y_1, Z_1, X_2, Y_2, Z_2 ≤ 10000 altı tam ədədini ehtiva edir və bu, (X_1, Y_1, Z_1) nöqtələrini (X_2, Y_2, Z_2) nöqtələri ilə birləşdirən bir xətt seqmentini (cockridor) bildirir. Sizə zəmanət verilir ki, seqmentin heç bir daxili nöqtəsi digər seqmentin son nöqtəsi deyil və həm başlanğıc, həm də son mövqelər ən azı bir seqmentin son nöqtələridir. Bütün koordinatlar metrlə verilir.
Çıxış verilənləri
Hər bir giriş instansiyası üçün Charlienin başlanğıc nöqtədən son nöqtəyə çatması üçün lazım olan ən qısa vaxtı verən bir real ədəd R çap edin. Charlie yalnız bütün düz seqmentlər boyunca hərəkət edə bilər, onların hamısı hər iki istiqamətdə istifadə edilə bilər. Hər hansı belə bir yol üçün vaxt R = L/S + D/T saniyədir, burada L keçilən bütün seqmentlərin uzunluqlarının cəmidir (metrlə) və D ardıcıl seqmentlər arasında dönmək üçün lazım olan bucaqların cəmidir (dərəcə ilə). Charlienin üzləşdiyi ilkin və son istiqaməti seçə bilərsiniz və həmişə başlanğıc nöqtədən son nöqtəyə ən azı bir yolun mövcud olduğunu qəbul edin.
Cavab, R ilə hakimlər tərəfindən hesablanan cavab arasındakı fərq ən çox 0.001 olduqda düzgün qəbul ediləcək.