Найкоротший маршрут польоту#3396
Комерційні рейси статистично досить безпечні (в термінах кількості смертей на пасажиро-кілометр, лише політ на Місяць безпечніший). Проте існують причини для запобіжних заходів і правил безпеки. Одним із ранніх таких правил було так зване правило " хвилин", яке вимагало, щоб двомоторний літак завжди знаходився в межах хвилин від найближчого відповідного аеропорту вздовж усього маршруту польоту. Існувала різноманітність подібних правил, але в основі вони залишаються однаковими: маршрут польоту не може віддаляти літак на певну максимальну дозволену відстань від найближчого аеропорту. Через ці обмеження літаки не завжди можуть використовувати прямий маршрут для польоту з одного аеропорту до іншого.
У цій задачі ми обчислимо найкоротший маршрут польоту між двома аеропортами, дотримуючись правила максимально дозволеної відстані. На малюнку нижче, який ілюструє перший зразок тестового випадку, будь-який маршрут польоту повинен залишатися в межах трьох кіл. Таким чином, літак, що летить з аеропорту до аеропорту , повинен об'їжджати прямий маршрут через регіон навколо аеропорту . Зверніть увагу, що літак не обов'язково повинен летіти до самого аеропорту .
Ситуація ускладнюється тим, що літаки мають обмежений запас пального, і для подолання більших відстаней їм може знадобитися зупинка в проміжних аеропортах. Таким чином, залежно від ємності бака, літак, що летить з аеропорту до аеропорту на малюнку, може бути змушений зупинитися в аеропорту (або ємність бака може бути занадто малою навіть для польоту до аеропорту , у такому випадку подорож буде неможливою).
Ми робимо такі спрощувальні припущення:
Поверхня землі є сферою радіусом км.
І час, і витрати пального прямо пропорційні пройденій відстані. Іншими словами, нас цікавить лише загальна пройдена відстань.
Різниця у відстані, викликана польотами літаків на різних висотах, є незначною. Таким чином, фактично, ми припускаємо, що вони летять уздовж поверхні землі.
Літак може зупинятися для дозаправки в стількох проміжних аеропортах, скільки потрібно, кожного разу отримуючи повний бак.
Перша строка кожного тестового випадку містить два цілі числа та , де 2 \le N \le 25 — це кількість аеропортів, а 1 \le R \le 10000 — це максимально дозволена відстань польоту (в км) від найближчого аеропорту. Кожна з наступних строк містить два цілі числа , , що задовольняють 0 \le \varphi < 360 та -90 \le \theta \le 90, довготу та широту (відповідно) аеропорту, у градусах. Аеропорти пронумеровані відповідно до їх порядку у вхідних даних, починаючи з одиниці. Жодні два аеропорти не знаходяться в одній і тій самій позиції.
Після цього йде строка, що містить ціле число , яке задовольняє 1 \le Q \le 100. Кожна з наступних строк містить три цілі числа , , , що задовольняють 1 \le s, t \le N, s \neq t, та 1 \le c \le 50000, що вказують на літак, який летить з аеропорту до аеропорту з ємністю бака, що дає запас ходу км.
Для кожного тестового випадку виведіть номер випадку, а потім одну строку для кожного запиту, що містить довжину в км найкоротшого маршруту польоту між аеропортами та , з урахуванням обмеження на пальне . Виведіть довжину з точністю до трьох десяткових знаків. Якщо немає допустимого маршруту між двома аеропортами, виведіть слово impossible замість цього.
Ви можете припустити, що відповідь є чисельно стабільною для збурень до км для або .
Приклад 1