Сферичні дзеркала
Давним-давно в галактиці, далеко-далеко звідси, існувало N сфер з різними радіусами.
Ці сфери були дзеркальними, тобто мали відбивні поверхні...
Ви знаходитесь в початку координат галактики (0, 0, 0) і випромінюєте лазерний промінь у напрямку (u, v, w). Промінь рухається по прямій лінії.
Коли лазерний промінь з I вдаряється об поверхню сфери в точці Q, нехай N буде точкою поза сферою на лінії, що з'єднує центр сфери і Q. Відбитий промінь йде в напрямку до R, що задовольняє наступні умови: (1) R знаходиться на площині, утвореній трьома точками I, Q і N, (2) IQN = NQR, як показано на Рисунку 1.
Рисунок 1: Відбиття лазерного променя
Після кількох відбиттів він нарешті виходить за межі нашого спостереження. Ваше завдання - написати програму, яка визначає останню точку відбиття.
Вхідні дані
Вхід складається з кількох наборів даних, кожен з яких має наступний формат.
N
u v w
x_1 y_1 z_1 r_1
...
x_N y_N z_N r_N
Перша строка набору даних містить додатне ціле число N, яке є кількістю сфер. Наступна строка містить три цілі числа u, v і w, розділені пробілами, де (u, v, w) - це напрямок лазерного променя, що спочатку випромінюється з початку координат.
Кожна з наступних N строк містить чотири цілі числа, розділені пробілами. i-та строка відповідає i-тій сфері, а числа представляють положення центру (x_i, y_i, z_i) і радіус r_i.
N, u, v, w, x_i, y_i, z_i і r_i задовольняють наступні умови.
1 ≤ N ≤ 100
−100 ≤ u, v, w ≤ 100
−100 ≤ x_i, y_i, z_i ≤ 100
5 ≤ r_i ≤ 30
u^2 + v^2 + w^2 > 0
Можна припустити, що відстань між поверхнями будь-яких двох сфер не менше 0.1. Також можна припустити, що початок координат (0, 0, 0) знаходиться поза будь-якою сферою і знаходиться на відстані не менше 0.1 від поверхні будь-якої сфери.
Відомо, що промінь відбивається від поверхонь сфер принаймні один раз і не більше п'яти разів. Можна припустити, що кут між променем і лінією, що з'єднує центр сфери і точку відбиття, відомий як кут відбиття (тобто θ на Рисунку 1), менше 85 градусів для кожної точки відбиття.
Останній набір даних супроводжується строкою, що містить один нуль.
Вихідні дані
Для кожного набору даних на вході ви повинні вивести x-, y- і z-координати останньої точки відбиття, розділені пробілами в одному рядку. Жоден рядок виводу не повинен містити зайвих символів.
Жодне значення координат у виводі не повинно мати похибку більше ніж 0.01.