Задача №3141. iCopter
В двухмерной игре для современных мобильных телефонов «iCopter» между Васей и Петей идет Bluetooth-сражение. Идет третий раунд. Он проходит с применением вертолётной техники в горном массиве.
Горный профиль в игре «iCopter» задается ломаной (x1, y1), (x2, y2), …, (xN, yN), координаты вершин которой удовлетворяют неравенствам x1 < x2 < … < xN. Начальные и конечные точки профиля расположены на уровне моря (y1 = yN = 0).
Над горами летают вертолет Васи и вертолет Пети. Вертолёт Васи находится в точке A с координатами (XA, YA), Пети — в точке B с координатами (XB, YB). Вертолет Васи производит выстрел снарядом с начальной скоростью, которая задается вектором с компонентами (VX , VY).
Полёт снаряда проходит по следующим законам движения (они определяют координаты снаряда в каждый момент времени до столкновения с горой t ≥ 0):
X = XA + VX * t
В данной версии компьютерной игры снаряд взрывается только от удара в гору. При взрыве снаряд поражает все цели на расстоянии не больше R от эпицентра взрыва. Вертолёт противника считается уничтоженным, если он находится в радиусе поражения.
Требуется написать программу, которая по заданному рельефу, скорости снаряда и координатам вертолётов определяет точку попадания снаряда в гору и уничтожен ли при этом вертолёт Пети.
В первой строке входного файла задается семь целых чисел – радиус поражения R (0 ≤ R≤ 10 000, координаты точки A, координаты точки B, компоненты вектора скорости снаряда VX, VY ( -104 ≤ VX≤ 104, VX ≠ 0, 0 < VY≤ 104). Точки Aи B различны.
Во второй строке находится натуральное число N – количество вершин ломаной (2 ≤ N≤ 100 000), которая задает горный профиль. Последующие N строк содержат координаты вершин ломаной (x1, y1), (x2, y2), …, (xN, yN).
Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x1 < x2 < … < xN и y1 = yN = 0, а также то, что снаряд всегда попадает в заданный горный профиль и координата точки попадания xП по оси X лежит в пределах
x1 ≤ xП ≤ xN.
В первой строке выведите координаты точки взрыва с точностью не менее 3 знаков после запятой. Во второй строке выведите «YES», если вертолёт Пети будет поражен взрывом, и «NO» в противном случае.
Ввод | Вывод |
|
|
|
|