Flappy Bird

All submissions for this problem are available.
Statement
The super annoying flappy bird is back! This time it has variations. The distance between each pipe, width of each pipe and the gap width of each pipe is not uniform. Consider the world as a 2D plane, the initial position of the flappy bird is given (x, y) also, for a unit distance horizontally, flappy bird can move at most M distance vertically. There will be N pipes ahead of flappy bird. All the pipes are vertically straight and all the gaps are horizontal. For each pipe four integers x1, x2, y1, y2 are given. x1 and x2 give xcoordinates of the width of the pipe, y1 and y2 give the ycoordinates of the width of the gap. If the bird touches the pipe or the ground, the game is over. You have to find the maximum score that can be obtained considering the bird flies optimally.
Note:
1. Score is the number of pipes crossed successfully.
2. All the values are integers, no floating point values are used to represent the points and distance travelled vertically also must be an integer.
3.Since the value M is the distance it can move atmost vertically, it can choose not to move vertically at all at any instant.
Constraints:
1 < T < 100
0 < x, y <= 10^9
0 <= x1, x2, y1, y2 <= 10^9; x1 < x2 and y1 < y2
also, all the x values are given in non decreasing order. i.e. ith pipe is always to the right of (i1)th pipe
1 <= N <= 1000
1 <= M <= 10^9
Input
First line contains T the number of test cases.
For each test case, 1st line contains four integers x, y, M and N.
N lines follow each containing 4 integers x1, x2, y1, y2
Output:
For each test case print a single integer, denoting the maximum score that can be obtained followed by a new line.
Sample Input:
1
1 2 1 4
2 4 2 4
5 7 2 5
8 9 4 7
11 12 8 9
Sample Output:
3
Author:  abacus_opc 
Tags  abacus_opc 
Date Added:  14032014 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 