[LeetCode]--223. Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Rectangle Area
Assume that the total area is never beyond the maximum possible value of int.

Assume that the total area is never beyond the maximum possible value of int.

Credits:
Special thanks to @mithmatt for adding this problem, creating the above image and all test cases.

这个题目重点就是要很精巧的处理好重叠的问题。

public int computeArea(int A, int B, int C, int D, int E, int F, int G,
            int H) {
        int area1 = (C - A) * (D - B);
        int area2 = (G - E) * (H - F);

        int overlapRegion = overlap(A, B, C, D, E, F, G, H);
        return area1 + area2 - overlapRegion;
    }

    private int overlap(int A, int B, int C, int D, int E, int F, int G, int H) {
        int h1 = Math.max(A, E);
        int h2 = Math.min(C, G);
        int h = h2 - h1;

        int v1 = Math.max(B, F);
        int v2 = Math.min(D, H);
        int v = v2 - v1;

        if (h <= 0 || v <= 0)
            return 0;
        else
            return h * v;
    }

别高兴太早哈，这个是不能Accept的，因为在这个测试案例(-1500000001, 0,
-1500000000, 1, 1500000000, 0, 1500000001, 1)
我Debug了一下，是int超出了范围。

public int computeArea(int A, int B, int C, int D, int E, int F, int G,
            int H) {
        int area1 = (C - A) * (D - B);
        int area2 = (G - E) * (H - F);

        int overlapRegion = overlap(A, B, C, D, E, F, G, H);
        return area1 + area2 - overlapRegion;
    }

    private int overlap(int A, int B, int C, int D, int E, int F, int G, int H) {
        // int h1 = Math.max(A, E);
        // int h2 = Math.min(C, G);
        // int h = h2 - h1;
        int h = Math.max(A, E) - Math.min(C, G);

        // int v1 = Math.max(B, F);
        // int v2 = Math.min(D, H);
        // int v = v2 - v1;
        int v = Math.max(B, F) - Math.min(D, H);

        if (h <= 0 || v <= 0)
            return 0;
        else
            return h * v;
    }

还有一种比较好的算法：

public int computeArea2(int A, int B, int C, int D, int E, int F, int G,
            int H) {
        int val = (C - A) * (D - B) + (G - E) * (H - F);
        if (E > C || G < A || F > D || H < B) {
            return val;
        }
        val -= (Math.min(C, G) - Math.max(A, E))
                * (Math.min(D, H) - Math.max(B, F));
        return val;
    }