Given a list containing N (1 <= N <= 10 ^ 5) rectangles and Q (1 <= Q <= 10 ^ 5) queries. The i-th query will give a point (u, v). I need to print the index of the smallest rectangle in the list that encloses that point.
- A rectangle is defined as two points (x1, y1) at the bottom left and (x2, y2) at the top right.
- x1, y1, x2, y2 are odd numbers.
- There are no two rectangles intersect with each other
- u, v are even numbers
- All coordinates in the input are integers from 1 to 5000, inclusive.
If the statement isn't clear enough, please tell me.
Seems like you can go through each of the rectangles and mark in a grid all points where both coordinated are even covered for each rectangle. Since rectangles do not intersect you will cover at most 6250000 points in total. Then you answer queries by looking up the grid.
If no two rectangles intersect. For each point there is exactly one rectangle enclosing ot or no rectangle at all.
So for each rectangle go to all the points in that rectangle at mark them with the index of this rectangle.
Overall at most 5000*5000 points are traversed(as no rectangles intersect) and queries can be answered in O(1).
Your first line is wrong. One rectangle may completely enclose a smaller one.