Задача A. Апексные гонки ≡

Условие

Вас взяли на работу в автомобильную компанию, которая участвует в гонках для рекламы своего продукта. В этом году спрос на гонщиков был выше обычного, и вашей компании достался потенциальный пилот Петя, который, однако, не умеет быстро просчитывать траектории. Вам необходимо ему в этом помочь и разработать идеальную траекторию для гонщика. Траекторией считается линия, описываемая центром автомобиля. Известно, что гоночный трек имеет постоянную ширину w и ровно n поворотов с заданными внешними радиусами R_i. В начальный момент времени координаты старта совпадают с центром автомобиля. В конце пути координаты финиша также будут совпадать с координатами центра автомобиля.

Было решено, что на прямых участках Петя будет ехать ровно по центру трека (в этом случае центр автомобиля совпадает с центром трека), а на поворотах по окружности, так, что автомобиль своим краем касается апекса (точка, ближайшая к внутреннему краю дороги). На границах трека установлены ограничители, поэтому выходить за его границы нельзя. Траектория считается корректной, только в том случае, когда каждый поворот удается начать из центра трека и закончить, доехав до центра трека.

Ваша задача написать программу, которая поможет определить угол поворота левого переднего колеса α_i для каждого поворота на треке. Именно это колесо задаёт движение автомобиля на этих гонках. Обратите внимание, что у разных колес будет свой угол поворота из-за того, что колеса описывают разные по радиусу окружности. Например, если левое колесо расположено ближе к апексу, то угол его поворота будет больше угла поворота правого колеса, т. к. левое колесо описывает окружность меньшего радиуса. Также необходимо подсчитать общую длину траектории s. Чем лучше и быстрее Вы справитесь, тем больше у вас шансов на повышение внутри компании!

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

В первой строке входного файла находятся 4 числа (x₁,y₁,x₂,y₂) - координаты переднего правого и левого заднего колеса автомобиля соответственно. Вторая строка содержит число w - ширину трека. В третьей строке даны два числа (x_f,y_f) - координаты финиша. В четвертой строке находится число n - количество поворотов. В следующих n строках находятся по 3 числа (X_i,Y_i,R_i) - координаты поворота в прямолинейной траектории и внешний радиус поворота.

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

В первой строке выходного файла содержится число s - длина получившейся траектории, которая округляется и выводится с точностью до 5-ого знака после запятой. В следующих n строках находятся значения α_i - угол поворота переднего левого колеса на i-ом повороте в радианах, который округляется и выводится с точностью до 5-ого знака после запятой. Если заданную траекторию построить невозможно, вывести только -1.

Ограничения

0 < w ≤ 1000
0 ≤ n ≤ 10⁴
 − 10⁶ < x₁,y₁,x₂,y₂,x_f,y_f,X_f,Y_f < 10⁶
w < R_i < 100

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

3 2 1 0
4
13 10
1
2 10 6

17.24700
0.13407

5 4 0 1
5.21
3 5.432
2
38.3553 38.3553 6.5
51.3362 -9.9137 6.5

134.91777
0.41026
0.41892

Задача 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

Задача C. Таксую для души ≡

Условие

Вася — таксист с большой душой. Он обожает водить машину, чувствовать город под колесами, но глубоко внутри он настоящий программист. Поэтому всем своим пассажирам он говорит, что является успешным программистом, а таксует так, для души.

Но именно сегодня навигатор у Вани сломался и теперь ему нужно быстро написать программу, которая найдёт кратчайший путь из точки A в точку B, дабы не опозориться перед пассажиром. Помогите ему в этом деле.

Город является прямоугольником с высотой H и шириной W, где каждая клетка — это перекрёсток. Всё было бы хорошо, но Вася знает, что сейчас в городе из-за аварий, ремонтов, пришельцев закрыты N перекрёстков с номерами a₁, a₂, ..., a_N. Нумерует перекрёстки он по принципу: a = i * w + j, когда перекрёсток на ходится на пересечении i улицы и j улицы.

Так же Вася напомнил, что существует правило проезда перекрёстка, которое гласит, что необходимо уступать всем машинам, что оказались справа. Поэтому если Вася подъезжает на перекрёсток, то дальше он может сразу (за 1 времени) повернуть направо, пропустить машину и проехать прямо (2 единицы времени), пропустить машину и справа встречную, а затем повернуть налево (3 единицы времени), пропустить машины со всех направлений и развернуться (4 единицы).

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

В первой строке подаются два целых числа: 1 ≤ H, W ≤ 3 * 10³, разделённые пробелом.

Во второй строке идут три целых числа: 1 ≤ A, B ≤ H * W, 0 ≤ N ≤ min(H, W) / 2.

В третей строке идут N целых чисел: 1 ≤ a_i ≤ H * W.

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

Выведите одно целое число — кратчайшее расстояние из точки A в точку B. Если добраться невозможно, то выведите -1.

Примечание

Вася может выбрать исходное направление движения своего такси.

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

10 10
1 50 5
3 14 23 32 41

-1

4 4
1 2 3
9 11 12

1