当前位置:首页 » 计算机算法

[LeetCode]--223.+Rectangle+Area

2016-10-11 23:02 本站整理 浏览(3)

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 * the maximum possible value of int.

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

Credits:

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

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

[code]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超出了范围。

[code]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;
    }
还有一种比较好的算法:

[code]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;
    }