Sponsored
Sponsored
This approach involves calculating the area of each rectangle separately, then finding the overlapping area, and subtracting it from the total. First, calculate the area of each rectangle by using the formula width multiplied by height. To find the overlap, determine the maximum of the bottom-left x and y coordinates, and the minimum of the top-right x and y coordinates. If the rectangles do intersect, subtract the overlap area from the sum of the rectangle areas to get the total covered area.
The time complexity is O(1) since it involves basic arithmetic operations, and the space complexity is also O(1) as no additional space is needed beyond a few variables.
1#include <stdio.h>
2
3int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
4 int area1 = (ax2 - ax1) * (ay2 - ay1);
5 int area2 = (bx2 - bx1) * (by2 - by1);
6 int overlapWidth = ((ax2 < bx2) ? ax2 : bx2) - ((ax1 > bx1) ? ax1 : bx1);
7 int overlapHeight = ((ay2 < by2) ? ay2 : by2) - ((ay1 > by1) ? ay1 : by1);
8 int overlapArea = 0;
9 if (overlapWidth > 0 && overlapHeight > 0) {
10 overlapArea = overlapWidth * overlapHeight;
11 }
12 return area1 + area2 - overlapArea;
13}
14
15int main() {
16 printf("%d\n", computeArea(-3, 0, 3, 4, 0, -1, 9, 2));
17 printf("%d\n", computeArea(-2, -2, 2, 2, -2, -2, 2, 2));
18 return 0;
19}This program first computes the rectangles' areas using their width and height. It then calculates the overlap width and height based on intersecting limits of x and y coordinates. If these intersections are valid (width and height are positive), it then computes the overlap area and subtracts it from the total area of both rectangles. Finally, it outputs the total area covered by the rectangles.
By using the coordinate sweep method, we can iterate through all points in a uniform grid covering both rectangles. This technique conceptualizes sweeping lines across the plane, adding and subtracting areas as intersections are counted. Use sorting and a plane-sweep technique to determine overlapping intervals more effectively.
The time complexity remains O(1) since it involves constant time computation, while the space complexity is also O(1) because it uses a constant number of variables.
1
class Solution {
public bool IsOverlapping(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
return !(ax1 >= bx2 || bx1 >= ax2 || ay1 >= by2 || by1 >= ay2);
}
public int ComputeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int area1 = (ax2 - ax1) * (ay2 - ay1);
int area2 = (bx2 - bx1) * (by2 - by1);
int overlapArea = 0;
if (IsOverlapping(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)) {
int overlapWidth = Math.Min(ax2, bx2) - Math.Max(ax1, bx1);
int overlapHeight = Math.Min(ay2, by2) - Math.Max(ay1, by1);
overlapArea = overlapWidth * overlapHeight;
}
return area1 + area2 - overlapArea;
}
static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.ComputeArea(-3, 0, 3, 4, 0, -1, 9, 2));
Console.WriteLine(solution.ComputeArea(-2, -2, 2, 2, -2, -2, 2, 2));
}
}The C# solution determines whether two rectangles overlap and computes their combined area by subtracting any overlap. Simplified conditional logic determines if rectangles meet overlap criteria based on bounding conditions.