Сферические зеркала
Давным-давно в далёкой-далёкой галактике существовали 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.