#P6901. Downhill Ski Target Navigation
Downhill Ski Target Navigation
Downhill Ski Target Navigation
A skier starts at the origin (0,0) with a lateral velocity of 0 and moves downhill in the positive \( y \)-direction with a constant vertical velocity \( v_y \). The skier's lateral acceleration is limited by \( a_{\max} \), meaning that at any moment the lateral acceleration \( a \) must satisfy \( |a| \leq a_{\max} \). Along the course there are several target locations given by their coordinates \( (x,y) \). The skier wants to pass over as many targets as possible. To pass over a target, the skier's trajectory must go through that target.
Assume that the skier can choose any lateral acceleration (subject to \( |a| \leq a_{\max} \)) and that the effect of the lateral acceleration accumulates over time. In particular, if the time difference between two points is \( \Delta t \), the maximum change in the lateral position that can be achieved is given by
\[
\Delta x_{\max} = \frac{1}{2} a_{\max} (\Delta t)^2.
\]
Since the skier moves with a constant vertical speed \( v_y \), the time to reach a point with vertical coordinate \( y \) is \( t = \frac{y}{v_y} \). Thus, from the starting position \( (0,0) \), a target \( (x,y) \) is reachable if \[ |x| \leq \frac{1}{2} a_{\max} \left(\frac{y}{v_y}\right)^2. \]
Moreover, if the skier has already passed through a target \( (x_1,y_1) \) and then intends to reach another target \( (x_2,y_2) \) with \( y_2 > y_1 \), letting \( \Delta t = \frac{y_2-y_1}{v_y} \), it is necessary that \[ |x_2 - x_1| \leq \frac{1}{2} a_{\max} \left(\frac{y_2-y_1}{v_y}\right)^2. \]
Your task is to compute the maximum number of targets the skier can pass over by selecting an appropriate sequence of targets (in increasing order of \( y \)).
inputFormat
The first line contains two floating-point numbers ( v_y ) and ( a_{\max} ) and an integer ( n ), where ( v_y ) is the constant vertical velocity, ( a_{\max} ) is the maximum lateral acceleration, and ( n ) is the number of targets. Each of the next ( n ) lines contains two floating-point numbers ( x ) and ( y ) representing the coordinates of a target.
outputFormat
Output a single integer denoting the maximum number of targets that can be passed over.
sample
1 1 4
-2 2
0 5
2 6
2 10
3