All submissions for this problem are available.
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 as (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 x-coordinates of the width of the pipe, y1 and y2 give the y-coordinates 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.
- Score is the number of pipes crossed successfully.
- All the values are integers, no floating point values are used to represent the points and distance travelled vertically also must be an integer.
- Since the value M is the distance it can move atmost vertically, it can choose not to move vertically at all at any instant.
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
For each test case print a single integer, denoting the maximum score that can be obtained followed by a new line.
Constraints1 < 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. i-th pipe is always to the right of (i-1)th pipe 1 <= N <= 1000 1 <= M <= 10^9
1 2 1 4
2 4 2 4
5 7 2 5
8 9 4 7
11 12 8 9
Look at the below image
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.