Racing Gems
Time limit2sMemory limit256 MB
Collect as many gems as possible while running upward with limited sideways speed from any start position.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Sorting, Binary search
- Solved
- No attempts yet
Problem
You are playing a racing game. Your character starts on the axis () and runs up the track, which is bounded by the line on one side and by the line on the other. You may start anywhere along the starting line, as long as the position is inside the track. The finish line is , and the game ends when you reach it.
Your vertical velocity is fixed at . Your horizontal velocity, on the other hand, can be any value between and , and you may change it at any time.
There is one gem at each of fixed points on the track. You want to collect as many gems as possible. How many gems can a single run collect?
Input
The first line contains four space separated integers , , , and (, , ).
Each of the next lines contains two space separated integers and , the coordinates of the th gem (, ). No two gems share a position.
The input does not contain a value for .
Output
Print, on a single line, the largest number of gems that can be collected during the race.