Задача B. Плавающие интерфейсы VR ≡

Условие

Юный программист Руслан занимается разработкой приложения виртуальной реальности, и, как в любом хорошем VR приложении, он хочет добавить пользовательский интерфейс, который бы плавно следовал за поворотом головы. Игрок находится внутри некоторой сферы S: x² + y² + z² = R². В начальный момент времени голова Игрока имеет координаты (xp0, yp0, zp0), взгляд исходит из центра головы и имеет направление l⃗ = (xd0, yd0, zd0), заданное вектором единичной длины.

Пользовательский интерфейс представляет собой пространственный прямоугольник шириной w и высотой h. Его центр в начальный момент времени совпадает с точкой пересечения луча, выходящего из центра головы по направлению l⃗, и сферы S.

В любой момент времени центр пользовательского интерфейса находится на поверхности сферы, а сам прямоугольник расположен в касательной плоскости к сфере S, таким образом, что его верхняя сторона всегда параллельна плоскости пола Oxy. Далее, игрок начинает произвольным образом двигаться и вращать головой так, что она не выходит за границы сферы.

Вам известна информация о положении головы (xpf, ypf, zpf) и направлении взгляда (xdf, ydf, zdf) для каждого кадра f = 1, 2, .... Если в какой-то кадр f_i − 1 точка пересечения взгляда и плоскости пользовательского интерфейса находится внутри или на границе прямоугольника, а в следующем кадре f_i – за его границей, то происходит запуск начала отсчёта задержки перед движением интерфейса в новое положение, которое составляет k кадров, начиная с f_i. Если до завершения отсчёта точка пересечения взгляда и плоскости пользовательского интерфейса вернулась в границы прямоугольника, то отсчёт сбрасывается, и процедура ожидания повторяется.

По прошествии задержки пользовательский интерфейс начинает своё движение. Рассмотрим произвольный кадр f_j. Пусть P = (xUIf_j, yUIf_j, zUIf_j) ∈ S – координаты центра пользовательского интерфейса, Q = (xsf_j, ysf_j, zsf_j) ∈ S – координаты пересечения взгляда со сферой. Тогда мы можем сопоставить точкам P и Q пары чисел (θ_P, φ_P) и (θ_Q, φ_Q). 0°  ≤ θ_X ≤ 180° для точки X вычисляется как угол между осью Oz и отрезком, соединяющим начало координат и точку X, 0°  ≤ φ_X < 360° вычисляется как угол между осью Ox и проекцией отрезка, соединяющего начало координат с точкой X, на плоскость Oxy (см. рис. 2).

Таким образом получаем двумерное пространство Oθφ. Если соединить точки (θ_P,φ_P) и (θ_Q, φ_Q) в этом пространстве кратчайшей прямой линией, то мы получим отрезок, задающий изменение от положения P до положения Q. Вдоль этой линии пользовательский интерфейс движется с постоянной скоростью v градусов в кадр. Длина отрезка в пространстве Oθφ измеряется с помощью евклидовой нормы. Вам необходимо рассчитать, какое положение, заданное углами, будет у центра пользовательского интерфейса в следующем кадре и переместить его туда в конце текущего кадра.

Далее наступает момент времени следующего кадра f_j + 1 и вышеописанная процедура повторяется для новых положений пользовательского интерфейса и пересечения взгляда со сферой. Как только в пространстве Oθφ расстояние до Q оказывается меньше, чем расстояние, проходимое интерфейсом за один кадр, пользовательский интерфейс фиксируется в пространстве и снова ожидает момент, при котором взгляд окажется за границей прямоугольника.

Помогите Руслану рассчитать, где будут находиться вершины прямоугольника пользовательского интерфейса в момент завершения расчёта последнего кадра.

Формат входного файла

В первой строке находятся 4 вещественных числа w,h,R,v и одно целое неотрицательное число k.

Следующая пара строк содержит по три вещественных числа в каждой: в первой даны числа (xp0, yp0, zp0) – начальное положение головы, во второй - (xd0, yd0, zd0) – начальное направление взгляда.

Затем для каждого f парами следуют строки: в первой даны числа (xpf, ypf, zpf) – текущее положение головы, во второй - (xdf, ydf,zdf) – текущее направление взгляда.

Формат выходного файла

Требуется вывести 4 строки, в каждой из которых содержится положение вершины прямоугольника пользовательского интерфейса. Первой выводится левая верхняя вершина, остальные – в порядке обхода по часовой стрелке (см. рис. 1).

Каждая координата округляется и выводится с точностью до 5-го знака после запятой.

Ограничения

Гарантируется, что центр пользовательского интерфейса и пересечения взгляда со сферой ни в какой момент времени не проходит через точки (0,0,R) и (0,0, − R).

Если существует два оптимальных пути движения, то выбирайте тот, который не проходит через скачок φ.

Примеры тестов

1 1 1 90 0
0 0 0
1 0 0
0 0 0
0 1 0

-0.50000 1.00000 0.50000
0.50000 1.00000 0.50000
0.50000 1.00000 -0.50000
-0.50000 1.00000 -0.50000

1 1 1 45 2
0 0 0
1 0 0
0 0 0
0 1 0
0 0 0
0 1 0
0 0 0
0 1 0
0 0 0
-1 0 0
0 0 0
0 1 0
0 0 0
0 1 0
0 0 0

-0.50000 1.00000 0.50000
0.50000 1.00000 0.50000
0.50000 1.00000 -0.50000
-0.50000 1.00000 -0.50000