Радость полета
Радость полета
Джейкобу нравится играть с его радиоуправляемым самолетом. Погода сегодня довольно ветреная, и Джейкобу приходится тщательно планировать полет. У него есть прогноз погоды - скорость и направление ветра на каждую секунду запланированного полета.
Самолет может развивать скорость до vmax
единиц в секунду в любом направлении. Ветер сдувает самолет следующим образом: если скорость самолета составляет (vx
, vy
), а скорость ветра (wx
, wy
), то самолет перемещается на (vx
+ wx
, vw
+ wy
) каждую секунду.
У Джейкоба имеется топливо ровно k секунд, и он хочет узнать, сможет ли самолет пролететь от начальной до конечной точки за это время. Если это возможно, то ему необходимо знать план полета: положение самолета после каждой секунды полета.
Входные данные
Первая строка содержит четыре целых числа Sx
, Sy
, Fx
, Fy
(-10000 ≤ Sx
, Sy
, Fx
, Fy
≤ 10000) - координаты начала и конца.
Вторая строка содержит три целых числа n, k и vmax
(1 ≤ n, k, vmax
≤ 10000) - количество условий изменения ветра, продолжительность полета Джейкоба в секундах и максимальная скорость самолета.
Следующие n строк описывают изменения условий ветра. i-ая строка содержит целые числа ti
, wxi
и wyi
- начиная с времени ti
ветер дует по вектору (wxi
, wyi
) каждую секунду (0 = t1
< ... < ti
< ti+1
< ... < k, sqrt(wxi^2
+ wyi^2
) ≤ vmax
).
Выходные данные
В первой строке выведите "Yes" если самолет Джейкоба сможет пролететь от начальной до конечной точки за k секунд, и "No" иначе.
Если полет возможен, в следующих k строках вывести план полета. В i-ой строке вывести два действительных числа x и y - координаты положения (Pi
) самолета после i-ой секунды полета.
План считается корректным, если для каждого i (1 ≤ i ≤ k) можно пролететь за одну секунду от Pi-1
до некоторой точки Qi
, такой что расстояние между Qi
и Pi
не превосходит 10-5
, где P0
= S. Расстояние между Pk
и F также не должно превосходить 10-5
.
1 1 7 4 2 3 10 0 1 2 2 2 0
Yes 3 2.5 5 2.5 7 4