Problem H
Racing Gems

You are playing a racing game. Your character starts at the X-axis line ($y=0$) and proceeds up the racetrack, which has a boundary at the lines $x=0$ and $x=w$. The finish is at $y=h$, and the game ends when you reach that line. You proceed at a fixed vertical velocity $v$, but you can control your horizontal velocity to be any value between $-v/r$ and $v/r$, where $r$ is a fixed ratio. You may change your horizontal velocity at any time, but your vertical velocity must remain fixed.

There are gems at specific points on the race track. Your job is to collect as many gems as possible (they all have the same value).

How many gems can you collect? You may start at any horizontal position you want (but your vertical position must be $0$ at the start).


Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line will contain four integers: $n$ ($1 \le n \le 10^5$) is the number of gems, $r$ ($1 \le r \le 10$) is the ratio of vertical velocity to maximum horizontal speed, $w$ ($1 \le w \le 10^9$) is the width of the track, and $h$ ($1 \le h \le 10^9$) is the height of the finish line. Following this will be $n$ lines, each containing an integer $x$ and $y$ coordinate ($0 \le x \le w$, $1 \le y \le h$), containing the coordinate of a gem. All gems will lie on the race track. None will be on the start line.


Output a single integer on a line by itself representing the maximum number of gems that you can collect.

Sample Input 1 Sample Output 1
5 1 10 10
8 8
5 1
4 6
4 7
7 9
Sample Input 2 Sample Output 2
5 1 100 100
27 75
79 77
40 93
62 41
52 45
Sample Input 3 Sample Output 3
10 3 30 30
14 9
2 20
3 23
15 19
13 5
17 24
6 16
21 5
14 10
3 6
CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in