• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
• This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode -223- Rectangular area

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

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:

• 
  $-10^4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4$

Idea 1: mathematical coordinate simulation

• Coordinate simulation excludes four non-intersecting cases
• And then sort the four coordinates to calculate the cross area

public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
            int a1 = ax2 - ax1;
            int b1 = ay2 - ay1;
            int s1 = Math.abs(a1 * b1);
            int a2 = bx2 - bx1;
            int b2 = by2 - by1;
            int s2 = Math.abs(a2 * b2);
            // Two uncrossed rectangle logic
            if (Math.max(ax1, ax2) <= Math.min(bx1, bx2) || Math.max(ay1, ay2) <= Math.min(by1, by2)) {
                return s1 + s2;
            }
            if (Math.min(ax1, ax2) >= Math.max(bx1, bx2) || Math.min(ay1, ay2) >= Math.max(by1, by2)) {
                return s1 + s2;
            }
            // There is crossover logic
            int[] x = new int[]{ax1, bx1, ax2, bx2};
            int[] y = new int[]{ay1, by1, ay2, by2};
            Arrays.sort(x);
            Arrays.sort(y);
            int cx = x[2] - x[1];
            int cy = y[2] - y[1];
            return s1 + s2 - Math.abs(cx * cy);
        }
Copy the code

• Time complexity O(1)
• Space complexity O(1)