GPS#11631

GPS

1 секунда

128 мегабайтів

Середня

Ви, як і багато інших людей, ймовірно, користувалися системою глобального позиціонування (GPS), але замислювалися, як вона працює насправді. GPS-позиціонування базується на наборі супутників, що обертаються навколо Землі. Усі супутники мають синхронізовані внутрішні годинники, і вони постійно передають показники своїх годинників на поверхню Землі радіохвилями. GPS-приймач одночасно отримує виміри з декількох супутників, які знаходяться в полі зору. Значення часу $t_{1}, \dots, t_{m}$ t_1, \ldots, t_m, отримані в момент часу $t$ , зазвичай різні, адже кожен супутник знаходиться на різній відстані до приймача. Оскільки ми знаємо точні орбіти всіх супутників, ми точно знаємо, де знаходився кожен супутник під час надсилання сигналу. Виходячи з цих позицій і відстаней, можна визначити своє місцезнаходження. Щоб однозначно визначити позицію за умови, що ви перебуваєте на поверхні Землі, потрібно мінімум $3$ вимірювання від супутників.

Однак ваше завдання — не визначити власну позицію, а з'ясувати, сигнали яких супутників ви отримали. Тобто: вам задано ваші географічні координати на Землі та опис усіх супутникових орбіт, і потрібно для кожного супутника визначити:

чи досягне вас сигнал, надісланий супутником у певний момент (це так, якщо сигнал не проходить крізь Землю);
якщо сигнал таки досягає вас — скільки часу він подорожує від супутника до вашої позиції.

Пам'ятайте, що радіохвилі поширюються прямолінійно зі швидкістю світла ( $299792458$ м/с). Вважаємо, що Земля — ідеальна сфера радіусом $6371$ км, а всі супутники GPS обертаються із сталою швидкістю ідеальними колами навколо центру Землі.

Вхідні дані

У першому рядку знаходиться число $s$ ( $1 \leq s \leq 1 0^{4}$ 1 \le s \le 10^4) — кількість супутників.

У наступному рядку — два дійсних числа $l_{o}, l_{a}$ l_o, l_a — довгота та широта вашої позиції.

Кожен із наступних $s$ рядків містить чотири дійсних числа $ϕ, ψ, r, x$ \phi, \psi, r, x, що описують один супутник.

Для довготи $l_{o} \in [- 180, 180]$ l_o \in [-180, 180] додатні значення означають схід, від'ємні — захід.

Для широти $l_{a} \in [- 90, 90]$ l_a \in [-90, 90] додатні значення означають північ, від'ємні — південь.

Формат опису супутників наступний:

$ϕ \in [- 180, 180]$ \phi \in [-180, 180] — опорна довгота, у якій орбіта перетинає екватор (кожна орбіта перетинає екватор щонайменше двічі). Додатна — схід, від'ємна — захід.
$ψ \in [0, 360]$ \psi \in [0, 360] — кут між площиною орбіти та екватором на довготі $ϕ$ . Значення між $0$ і $180$ відповідають руху на північ, між $180$ і $360$ — на південь. Якщо орбіта лежить у площині екватора, $ψ = 0$ \psi = 0 або $180$ .
$r \in [7000, 1 0^{6}]$ r \in [7000, 10^6] — радіус орбіти супутника у кілометрах.
$x \in [0, 1)$ x \in [0, 1) — частка орбіти, здійснена супутником від точки перетину з екватором у $ϕ$ на момент відправки сигналу.

Схематичне зображення координат супутника. Орбіта супутника показана червоним кольором, реальна точка — це фактичне розташування. На Землі екватор і нульовий меридіан відмічені лініями. Пунктирна лінія — копланарна екватору і має той самий радіус, що й орбіта супутника. Кути $ϕ$ та $ψ$ визначені у вхідних даних. Чорна точка — ваше місцезнаходження на Землі, і потрібно визначити час, необхідний сигналу для руху по синій лінії.

Примітка: Усі дійсні числа у вхідних даних мають не більше $3$ знаків після десяткової крапки. Гарантується, що кожен супутник знаходиться мінімум за $1$ метр від дотичної площини у вашій точці (це дозволяє безпечно використовувати обчислення із плаваючою комою).

Вихідні дані

Для кожного супутника нічого не виводьте, якщо сигнал, надісланий цим супутником, вас не досягає. Якщо сигнал таки доходить до вас, виведіть час, необхідний сигналу для подорожі від супутника до вас у секундах. Час повинен бути точним із відносною чи абсолютною похибкою (яка з них менше) не більше $1 0^{- 7}$ 10^{-7}.

Приклади

Приклад 1