Last Updated: 13 Feb, 2021
Attack On Titans
Moderate
Asked in company
Levi Ackerman implements a new strategy for the protection of his kingdom. For this, he assigns a few beast titans, on each level, a titan defends the Kingdom that is represented by a rectangular grid of cells. If a titan takes a position in some cells of the grid, then this titan defends all the cells in the same row and the same column. No two titans share a row or a column. The penalty of the position is the number of cells in the largest undefended rectangle.
For example
The given figure has titans at coordinates at (3,8) and (8,6) and (11,2). We can see that the maximum undefended rectangle is of area 12 units, therefore, the position shown in the picture has a penalty of 12.
Help Levi to find out how much the penalty will cost the given positions of titans.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains three space-separated integers L, B, and N that are the length of the grid, breadth of the grid, and a number of beast titans, respectively.
The next N lines of each test case contain two space-separated integer numbers X and Y that represent the coordinates of the cell occupied by a titan.
Output format :
For each test case, in a separate line, print a single integer which is the penalty of the given configuration.
Note:
You don’t have to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= L, B <= 3000
0 <= N <= MIN(L,B)
1 <= X <= L
1 <= Y <= B
Time Limit : 1 sec
Approaches
The idea is to find the area of all possible rectangles formed by the configuration that is every rectangle formed between any four belts of titan reign(that titan can protect) and tore the maximum area out of all the rectangles.
- First, we will put all the x coordinates of the titans in an array and also add 1 and the L in the array for the boundary points.
- Similarly, we will store the y coordinates of the titans in an array and here also add 1 and B in the array for boundary points.
- Now sort both the arrays.
- To calculate the area we will pairwise calculate the area, for every consecutive pair in x coordinates we will iterate for every pair in y coordinates array. For example, if x coordinate array is {1,2,3} and y coordinate array is {4,7,8} then we will calculate the area between 1, 2 and 4, 7 and then 1, 2 and 7, 8 and in this fashion for all other numbers.
- The area will be (X[i] - X[i-1] -1) * (Y[j] - Y[j-1] -1).
- And in each iteration, we will update the maximum area.
- Finally, return the maximum area.
The idea is to consider the maximum gap between the x coordinates as well as y coordinates and then finding the maximum area by multiplying these maximum gaps.
- First, we will put all the x coordinates of the titans in an array and also add 1 and the L in the array for the boundary points.
- Similarly, we will store the y coordinates of the titans in an array and here also add 1 and B in the array for boundary points.
- Sort both the arrays.
- Calculate the difference between every consecutive x coordinates and find the maximum difference of all.
- Do the above step for the y coordinates also.
- After calculating both the maximums, calculate the area.
- Area = (maximum difference of x coordinates -1) * (maximum difference of y coordinates -1).
- Return the 'area'.