Tester: Aditya Sarode
Editorialist: Aditya Sarode
Given N rectangles and M points in a co-ordinate plane, each of the point belongs to a single rectangle such that the point lies in or on the rectangle. Find the maximum value of points which can belong to a particular rectangle.
We first find the maximum number of points which can belong to each of the N rectangles, considering that all the points which lie on it’s sides or vertices belong to itself, and not to the rectangles surrounding it and store it into points[N] array.
And the maximum of the values of these rectangles will be the answer.
Each point can belong to atmost 4 rectagles.
We can maintain a 3D array, array[x][y]: which denotes the rectangles to which the co-ordinate point (x,y) can belong, the 3rd dimension is used for storing the index of the corresponding rectangle.
We will find this for all x and y such that 1<=x<=500 and 1<=x<=500.
The array can be built by iterating through all the co-odinate points in and on each of the N rectangles.
And as we take the input of points, we can find all the rectangles ( Max. 4 ) to which the point can belong in O(1) from the built 3D array, and add the point to each of the rectangles, by adding it to the points array.
points[i] will now contain the maximum number of points which can belong to ith rectangle.
The maximum of this array is the answer
Complexity: O( A + M ).
Where A = Sum of number of co-ordinate points lying in or on each of the rectangle