Problem of the day
New update is available. Click here to update.
Last Updated: 1 Jul, 2021
Magic Park
Hard
Bob came to a magic aqua park. In this magic aqua park, There are N props. Each prop is a non-horizontal and non-vertical segment. So when Bob falls on the segment, he starts sliding on it, and when he reaches its lowest point, he continues falling vertically. Then he can fall on another segment and so on until he reaches the water. He knows his initial X coordinate, and he is at a very high altitude. Help Bob to find his final X coordinate.
For Example:
Input
4 2
0 1 2 2
2 4 4 5
Output
0
Explanation:
Here, Bob will first fall on the second prop, and he will travel till endpoint 2. Then he will fall on the first prop and travel till the endpoint 0. hence the final position will be X = 0.
Input Format:
The first line contains a single integer 'T' denoting the number of tests cases to be run. Then the test cases follow.
The first line of each test case contains two space-separated integers - initial X coordinate and N - number of segment props.
The next N lines of each test case describe the prop each by four integers x1, y1, x2, y2 - denoting the coordinates of the leftmost and rightmost point of the prop, respectively.
Note:
Props do not intersect or touch each other.
Output Format:
For each test case, print an integer βAβ denoting the final
coordinate
of Bob.
Answers for each test case will be printed in a separate line.
Note
You are not required to print anything; it has already been taken
care of. Just implement the function and return the answer.
Constraints:
1 <= T <= 50
1 <= N <= 100
0 <= X <= 104
0 <= X1, Y1, X2, Y2 <= 10000
x1 < x2
Time Limit: 1 sec.
Approaches
Let us see the process described in the statement. First, we can say that Bobβs Y-coordinate is at infinity and check if there is some prop behind. If there are none of them - this X-position is final for him. Otherwise, he will fall on some prop below, roll down from one of its ends, and have a similar problem.
Let us check every prop. For every prop, we can check that it is entirely to the left from us or entirely to the right from us; if it is - this means that for sure the given object is not below. If the projection of our point on the X-axis lies on the projection of an object on the X-axis - let's find the Y-coordinate of the segment at the given X-coordinate.
If this coordinate is more significant than the X-coordinate of our point - it means that the segment is actually above us (even if the lowest endpoint has a smaller Y-coordinate than our point).
Otherwise, it is below us - but it is possible that we will not fall on this segment because there is some other segment between us.
Let us pick among all segments below us one with the largest Y-coordinate at a given X-coordinate - Bob will fall on this segment.
Algorithm
- Declare a variable Y and initialize it will 1e9.
- Run a while loop with parameter true inside while.
- Inside the while loop make a variable id and call function find() and store value returned by it in id.
- Make a global array vis of size n and initialize it with 0.
- The function find() makes two variables res and best of type int and of type double and initializes them with -1.
- Run a loop from 1 to n and inside the loop check if the current index is already visited or coordinates of the current prop are not in range and continue according to that.
- Make a variable AT and store the slope of current points in it.
- Continue if AT is greater than Y.
- If AT is greater than best, then update the best and res values accordingly.
- Update the variable according to the vis of res index.
- return result from find() function.
- Now, inside, while checking if id is not -1 if it is, then break the while loop.
- Make function get_lower() and store its return value inside a pair at.
- Inside get_lower() return the min pair of passed two-point pairs.
- Update the X and Y values with the values returned by get_lower()
- After a while, return the variable X.
Download our app:
FOLLOW US ON
We accept payments using:
