P7069 [NWRRC 2014] Joy of Flight

Jacob likes to play with his radio-controlled aircraft. The weather today is pretty windy and Jacob has to plan flight carefully. He has a weather forecast — the speed and direction of the wind for every second of the planned flight. The plane may have airspeed up to $v_{\max}$ units per second in any direction. The wind blows away plane in the following way: if airspeed speed of the plane is $(v_x, v_y)$ and the wind speed is $(w_x, w_y)$, the plane moves by $(v_x+w_x, v_y+w_y)$ each second.  Jacob has a fuel for exactly $k$ seconds, and he wants to learn, whether the plane is able to fly from start to finish in this time. If it is possible he needs to know the flight plan: the position of the plane after every second of flight.

The first line of the input file contains four integers $S_x, S_y, F_x, F_y$ — coordinates of start and finish ($−10 000 ≤ S_x, S_y, F_x, F_y ≤ 10 000$). The second line contains three integers $n, k$ and $v_{\max}$ — the number of wind condition changes, duration of Jacob’s flight in seconds and maximum aircraft speed ($1 ≤ n, k, v_{\max} ≤ 10 000$). The following $n$ lines contain the wind conditions description. The $i$-th of these lines contains integers $t_i, w_{x_i}$ and $w_{y_i}$ — starting at time $t_i$ the wind will blow by vector $(w_{x_i}, w_{y_i})$ each second ($0 = t_1 < ··· < t_i < t_{i+1} < ··· < k; \sqrt{w_{x_i}^2 + w_{y_i}^2} ≤ v_{\max}$).

The first line must contain `Yes` if Jacob’s plane is able to fly from start to finish in k seconds, and `No` otherwise. If it can to do that, the following $k$ lines must contain the flight plan. The $i$-th of these lines must contain two floating point numbers $x$ and $y$ — the coordinates of the position ($P_i$) of the plane after $i$-th second of the flight. The plan is correct if for every $1 ≤ i ≤ k$ it is possible to fly in one second from $P_{i−1}$ to some point $Q_i$, such that distance between $Q_i$ and $P_i$ doesn’t exceed $10^{−5}$, where $P_0 = S$. Moreover the distance between $P_k$ and $F$ should not exceed $10^{-5}$ as well.

Time limit: 2 s, Memory limit: 256 MB.