10381번 - 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⁻⁵, where \(P_0\) = \(S\). Moreover the distance between \(P_k\) and \(F\) should not exceed 10^-5 as well.