Радість польоту#7501

Радість польоту

1 секунда

128 мегабайтів

Дуже легка

Джейкобу подобається грати зі своїм радіокерованим літаком. Сьогодні погода досить вітряна, тому Джейкобу потрібно ретельно планувати політ. У нього є прогноз погоди, який містить швидкість і напрямок вітру на кожну секунду запланованого польоту.

Літак може розвивати швидкість до $v_{ma x}$ v_{max} одиниць за секунду в будь-якому напрямку. Вітер впливає на літак так: якщо швидкість літака становить $(v_{x}, v_{y})$ (v_x, v_y), а швидкість вітру $(w_{x}, w_{y})$ (w_x, w_y), то літак переміщується на $(v_{x} + w_{x}, v_{y} + w_{y})$ (v_x + w_x, v_y + w_y) кожну секунду.

У Джейкоба є паливо рівно $k$ секунд, і він хоче дізнатися, чи зможе літак пролетіти від початкової до кінцевої точки за цей час. Якщо це можливо, йому потрібно знати план польоту: положення літака після кожної секунди польоту.

Вхідні дані

Перший рядок містить чотири цілі числа $S_{x}$ S_x, $S_{y}$ S_y, $F_{x}$ F_x, $F_{y}$ F_y ( $- 10000 \leq S_{x}, S_{y}, F_{x}, F_{y} \leq 10000$ -10000 \le S_x, S_y, F_x, F_y \le 10000) - координати початку і кінця.

Другий рядок містить три цілі числа $n$ , $k$ і $v_{ma x}$ v_{max} ( $1 \leq n, k, v_{ma x} \leq 10000$ 1 \le n, k, v_{max} \le 10000) - кількість умов зміни вітру, тривалість польоту Джейкоба в секундах і максимальна швидкість літака.

Наступні $n$ рядків описують зміни умов вітру. $i$ -ий рядок містить цілі числа $t_{i}$ t_i, $w_{x i}$ w_{xi} і $w_{y i}$ w_{yi} - починаючи з часу $t_{i}$ t_i вітер дме за вектором $(w_{x i}, w_{y i})$ (w_{xi}, w_{yi}) кожну секунду ( $0 = t_{1} < \dots < t_{i} < t_{i + 1} < \dots < k$ 0 = t_1 < \ldots < t_i < t_{i+1} < \ldots < k, $w_{x i}^{2} + w_{y i}^{2} \leq v_{ma x}$ \sqrt{w_{xi}^2 + w_{yi}^2} \le v_{max}).

Вихідні дані

У першому рядку виведіть "Yes", якщо літак Джейкоба зможе пролетіти від початкової до кінцевої точки за $k$ секунд, і "No" інакше.

Якщо політ можливий, у наступних $k$ рядках виведіть план польоту. У $i$ -му рядку виведіть два дійсних числа $x$ і $y$ - координати положення ( $P_{i}$ P_i) літака після $i$ -ої секунди польоту.

План вважається коректним, якщо для кожного $i$ ( $1 \leq i \leq k$ 1 \le i \le k) можна пролетіти за одну секунду від $P_{i - 1}$ P_{i-1} до деякої точки $Q_{i}$ Q_i, такої що відстань між $Q_{i}$ Q_i і $P_{i}$ P_i не перевищує $1 0^{- 5}$ 10^{-5}, де $P_{0} = S$ P_0 = S. Відстань між $P_{k}$ P_k і $F$ також не повинна перевищувати $1 0^{- 5}$ 10^{-5}.

Приклади

Приклад 1