RECT - Editorial ( NCC 2014 )

PROBLEM LINK:

Contest

Practice

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

2 Likes