### PROBLEM LINK:

**Author:** Vaibhav Tulsyan, Aditya Sarode

**Tester:** Aditya Sarode

**Editorialist:** Aditya Sarode

### DIFFICULTY:

EASY

### PROBLEM:

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.

### EXPLANATION:

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][4]: 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

Pseudo code:

Complexity: O( A + M ).

Where A = Sum of number of co-ordinate points lying in or on each of the rectangle