#P6901. Downhill Ski Target Navigation

    ID: 20108 Type: Default 1000ms 256MiB

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