Last Updated: 3 Apr, 2021
Rectangle Area
Ninja
Asked in companies
You are given a list of rectangles where each rectangle is represented by an array of four integers (i.e. Rectangle[i]=[x1, y1, x2, y2], where x1, y1 represents the bottom left point of the rectangle and x2.y2 represents the top right point of the rectangle, you have to find the total area covered by all the rectangles in the plane.
Example :
Rectangles = [[0, 0, 2, 2], [1, 0, 2, 3],[1, 0, 3, 1]],
For the given three rectangles, you can observe that the first rectangle occupies an area of 4 units and the second rectangle has an area of 3 units, but we have to keep one thing also in mind that they have an area of 3 units common overlapping among them, so we cannot include it again, so the final area which comes out for all the rectangles is 6 units.
Total Area = 6 units
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains an integer N representing the size of the Array of rectangles.
The next N lines consist of 4 integers representing the bottom left and top right coordinate points of each rectangle.
Output Format :
For each test case, return the area of all the rectangles. To avoid any overflows, return the answer Modulo 10^9+7.
You do not need to take input or print anything. This already has been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <=200
0 <= x1, y1, x2 , y2 <= 10^9 where x1.y1 is the bottom left coordinate of rectangle and x2,y2 is top right corner of rectangle.
Time Limit 1 second.
Approaches
- As we can have only 200 distinct rectangles with us so we don’t need to worry about point constraint, we can use the coordinate compression technique to map these points all The x-axis points and y-axis points as well.
- Now these mapped coordinates can be used to form our grid. we can make a grid grid[x][y] = True for rx1 <= x < rx2 and ry1 <= y < ry2. Where rx1 , rx2, ry1, ry2 correspond to compressed coordinates.
- Afterwards, each grid[rx][ry] represents the area (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), where if x got remapped to rx, then imapx(rx) = x ("inverse-map-x of remapped-x equals x"), and similarly for imapy.
- Make a segment tree that supports the following operations:
- incrementing a range by 1
- decrementing a range by 1
- and the query is: how many non zero elements are active in the array,(that means how many y coordinates are active at this moment)
- so for each event at coordinate x2 and the previous event is x1
- add (x2-x1) * tree.query() to your union area
- then update the tree according to this event