Total area of overlapping rectangles

Easy
0/40
Average time to solve is 10m
profile
Contributed by
8 upvotes
Asked in companies
MicrosoftSAP LabsOracle

Problem statement

You are given two arbitrary rectangles on a 2-D coordinate plane, which may have an intersecting area. You have to find the net area covered by both the rectangles on the cartesian plane.

explain_image

The orange area depicted in the above figure is the net area covered by both rectangles on the cartesian plane.

Note:

1. For a rectangle, its top left and bottom right coordinates are given.

2. Coordinates of the rectangles are integer values.

3. Edges of the given rectangles will always be parallel to the X and Y coordinate axes of the cartesian plane.

4. It is guaranteed that both the rectangles will have at least a unit area.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains 4 space-separated integer values 'x1', 'y1', 'x2', 'y2' denoting the top left ('x1', 'y1') and bottom-right ('x2', 'y2') coordinates of the first rectangle.

The second line of each test case contains 4 space-separated integer values 'x3', 'y3', 'x4', 'y4' denoting the top left ('x3', 'y3') and bottom-right ('x4', 'y4') coordinates of the second rectangle.
Output Format: 
For each test case, return an integer denoting the net area of two rectangles.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10^5
-10^9 <= x1, y1, x2, y2 <= 10^9    
x1 < x2, x3 < x4
y1 > y2, y3 > y4

Time Limit: 1sec
Sample Input 1:
1
-1 0 3 -1
2 0 4 -3
Sample Output 2:
9
Explanation for Sample Output 1:

explanation_input1

In the above figure, the area of the green rectangle is 4 units, the area of the violet rectangle is 6 units and the intersecting area is 1 unit marked by the red rectangle. So, the total area of the overlapping rectangles is 9 units.
Sample Input 2:
1
1 2 2 1
-1 2 2 1
Sample Output 2:
3
Approaches (1)
Brute force, Geometry.
  • The problem is essentially two questions:
  1. How to know if the two rectangles have an intersecting area? Because if they do have some common area we need to subtract it from our final answer.
  2. If the two rectangles have a common area, how to find it?

 

  • Let’s consider two rectangles rectangle1 and rectangle2. Where left-most top point and right-most bottom point of rectangle1 are ('x1', ‘y1’), ('x2', ‘y2’). And the same for rectangle2 are ('x3', ‘y3’), ('x4', ‘y4’).
  • To know if two rectangles have some common area, we need to consider only four situations: ‘x1’ >= ‘x4’ or ‘y1’ <= ‘y4’ or ‘x2’ <= ‘x3' or ‘y2’ >= ‘y3’. In such cases, rectangle ('x1', ‘y1’, ‘x2’, ‘y2’) will not overlap with the rectangle ('x3', ‘y3’, ‘x4’, ‘y4’).
  • To calculate the common area, we only need to know the coordinates of the bottom left corner and top right corner of the overlapped area.
  • In any case we only need to know max('x1', ‘x3’), min('x2', ‘x4’), max('y1', ‘y3’) and min('y2', ‘y4’)  to calculate the overlapped area.
  • Net area = Area of rectangle 1 + Area of rectangle 2 - Intersection or Overlapped area.
Time Complexity

O(1)

 

Since all operations take constant time. Thus the time complexity will be O(1).

Space Complexity

O(1)

 

Since we are using constant extra memory. Thus the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Total area of overlapping rectangles
Full screen
Console