Сферичні дзеркала#5790

Сферичні дзеркала

1 секунда

64 мегабайти

Дуже складна

Давним-давно в галактиці, далеко-далеко звідси, існувало N сфер з різними радіусами.

Ці сфери були дзеркальними, тобто мали відбивні поверхні...

Ви знаходитесь в початку координат галактики $(0, 0, 0)$ (0, 0, 0) і випромінюєте лазерний промінь у напрямку $(u, v, w)$ (u, v, w). Промінь рухається по прямій лінії.

Коли лазерний промінь з $I$ вдаряється об поверхню сфери в точці $Q$ , нехай $N$ буде точкою поза сферою на лінії, що з'єднує центр сфери і $Q$ . Відбитий промінь йде в напрямку до $R$ , що задовольняє наступні умови: (1) $R$ знаходиться на площині, утвореній трьома точками $I$ , $Q$ і $N$ , (2) $I QN = N QR$ IQN = NQR, як показано на Рисунку 1.

Рисунок 1: Відбиття лазерного променя

Після кількох відбиттів він нарешті виходить за межі нашого спостереження. Ваше завдання - написати програму, яка визначає останню точку відбиття.

Вхідні дані

Вхід складається з кількох наборів даних, кожен з яких має наступний формат.

$N$

$u$ $v$ $w$

$x_{1}$ x_1 $y_{1}$ y_1 $z_{1}$ z_1 $r_{1}$ r_1

$\dots$

$x_{N}$ x_N $y_{N}$ y_N $z_{N}$ z_N $r_{N}$ r_N

Перший рядок набору даних містить додатне ціле число $N$ , яке є кількістю сфер. Наступний рядок містить три цілі числа $u$ , $v$ і $w$ , розділені пробілами, де $(u, v, w)$ (u, v, w) - це напрямок лазерного променя, що спочатку випромінюється з початку координат.

Кожен з наступних $N$ рядків містить чотири цілі числа, розділені пробілами. $i$ -тий рядок відповідає $i$ -тій сфері, а числа представляють положення центру $(x_{i}, y_{i}, z_{i})$ (x_i, y_i, z_i) і радіус $r_{i}$ r_i.

$N$ , $u$ , $v$ , $w$ , $x_{i}$ x_i, $y_{i}$ y_i, $z_{i}$ z_i і $r_{i}$ r_i задовольняють наступні умови.

$1 \leq N \leq 100$ 1 \le N \le 100

$- 100 \leq u, v, w \leq 100$ -100 \le u, v, w \le 100

$- 100 \leq x_{i}, y_{i}, z_{i} \leq 100$ -100 \le x_i, y_i, z_i \le 100

$5 \leq r_{i} \leq 30$ 5 \le r_i \le 30

$u^{2} + v^{2} + w^{2} > 0$ u^2 + v^2 + w^2 > 0

Можна припустити, що відстань між поверхнями будь-яких двох сфер не менше $0.1$ . Також можна припустити, що початок координат $(0, 0, 0)$ (0, 0, 0) знаходиться поза будь-якою сферою і знаходиться на відстані не менше $0.1$ від поверхні будь-якої сфери.

Відомо, що промінь відбивається від поверхонь сфер принаймні один раз і не більше п'яти разів. Можна припустити, що кут між променем і лінією, що з'єднує центр сфери і точку відбиття, відомий як кут відбиття (тобто $θ$ на Рисунку 1), менше $85$ градусів для кожної точки відбиття.

Останній набір даних супроводжується рядком, що містить один нуль.

Вихідні дані

Для кожного набору даних на вході ви повинні вивести $x$ -, $y$ - і $z$ -координати останньої точки відбиття, розділені пробілами в одному рядку. Жоден рядок виводу не повинен містити зайвих символів.

Жодне значення координат у виводі не повинно мати похибку більше ніж $0.01$ .

Приклади

Приклад 1