This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Topic describes

This is the area of 223 rectangles on LeetCode with medium difficulty.

Tag: “Inclusive exclusion principle”

You are given two rectangles made of straight lines on a two-dimensional plane. Calculate and return the total area covered by the two rectangles.

Each rectangle is represented by the coordinates of its lower left and upper right vertices:

  • The first rectangle is defined by its lower left vertex (ax1, ay1) and upper right vertex (ax2, ay2).
  • The second rectangle is defined by its lower left vertex (bx1, by1) and upper right vertex (bx2, by2).

Example 1:

Ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2 Output: 45Copy the code

Example 2:

Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2Copy the code

Tip:

  • –
    1 0 4 < = a x 1 , a y 1 , a x 2 , a y 2 , b x 1 , b y 1 , b x 2 , b y 2 < = 1 0 4 10^4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4

A class principle

First, given the lower left and upper right vertices, compute the area of the rectangle as (x2− X1)∗(y2−y1)(X2-x1) * (y2-y1)(x2− X1)∗(y2−y1).

So, we can start by directly calculating the areas of a given rectangle, AAA and BBB, and adding them up.

The rest, we need to find the intersection area of the two rectangles, using the “exclusion principle”, minus the intersection area, that is the answer.

Finding the area of the intersecting rectangles can be converted to finding the coincidence length of the two rectangles on the coordinate axis if the two rectangles are at
X X The coincidence length on the axis is zero
x x In the
Y Y The coincidence length on the axis is zero
y y , then the overlap area is
C = x ∗ y C = x * y . At the same time, if the two rectangles have no coincidence length on any coordinate axis, there is no coincidence area. Therefore, it is necessary to combine the coincidence length with
0 0 取
max ⁡ \max .

The final answer is A+B−CA + B-CA +B−C.

Code;

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int x = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
        int y = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
        return(ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1) - (x * y); }}Copy the code
  • Time complexity: O(1)O(1)O(1)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.223 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode by the start date, some of which have locks, so we will finish all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.