Чарлі Хрущ
Чарлі вміє літати. Проте, коли він хоче переміститися з однієї точки в іншу, це стає для нього виснажливим завданням. Основна проблема в тому, що Чарлі — хрущ. І, як відомо, всі хрущі (не плутати з тарганами) незграбні та повільні. Вони не тільки потребують часу, щоб летіти по прямій лінії, але й витрачають більше часу на повороти. Знаючи їх обмеження, чи зможете ви допомогти Чарлі знайти найшвидший маршрут?
Вхідні дані
Вхідні дані складаються з кількох тестових випадків. Перша строка кожного випадку містить цілі числа N, S та T (1 ≤ N ≤ 1000, 1 ≤ S, T ≤ 1000), де N — кількість прямих траєкторій польоту хруща (також відомих як "хрущидори"), S — швидкість Чарлі в метрах за секунду, а T — швидкість його повороту в градусах за секунду. Друга строка містить шість цілих чисел (0 ≤ X_f, Y_f, Z_f, X_t, Y_t, Z_t ≤ 10000), що вказують на початкову точку (X_f, Y_f, Z_f) та пункт призначення (X_t, Y_t, Z_t).
Кожна з наступних N строк містить шість цілих чисел 0 ≤ X_1, Y_1, Z_1, X_2, Y_2, Z_2 ≤ 10000, які вказують, що існує відрізок (хрущидор), що з'єднує точки (X_1, Y_1, Z_1) з (X_2, Y_2, Z_2). Гарантується, що жодна внутрішня точка відрізка не є кінцевою точкою іншого відрізка, і що як початкова, так і кінцева позиції є кінцевими точками принаймні одного з відрізків. Усі координати задані в метрах.
Вихідні дані
Для кожного вхідного випадку виведіть один рядок, що містить одне дійсне число R, яке дає найкоротший час, необхідний Чарлі, щоб дістатися від початкової до кінцевої точки. Чарлі може рухатися лише вздовж цілих прямих відрізків, усі з яких можуть використовуватися в обох напрямках. Час для будь-якого такого шляху дорівнює R = L/S + D/T секунд, де L — це сума довжин усіх пройдених відрізків (у метрах), а D — сума кутів, необхідних для повороту між послідовними відрізками (у градусах). Ви можете вибрати початковий та кінцевий напрямок, в якому Чарлі дивиться, і припустити, що завжди існує принаймні один шлях від початкової до кінцевої точки.
Відповідь буде прийнята як правильна, якщо різниця між R та відповіддю, обчисленою суддями, не перевищує 0.001.