Alibi

My Life is Getting Better

Leetcode[223] Rectangle Area

21 Nov 2015

###Task1 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.

###Python

class Solution(object):
    def computeArea(self, A, B, C, D, E, F, G, H):
        """
        :type A: int
        :type B: int
        :type C: int
        :type D: int
        :type E: int
        :type F: int
        :type G: int
        :type H: int
        :rtype: int
        """
        sums = (C - A) * (D - B) + (G - E) * (H - F)
        return sums - max(min(C, G) - max(A, E), 0) * max(min(D, H) - max(B, F), 0)

###Java

public class Solution {
    
    class Interval {
        int start;
        int end;
        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    
    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);
        Interval x1 = new Interval(A, C);
        Interval y1 = new Interval(B, D);
        Interval x2 = new Interval(E, G);
        Interval y2 = new Interval(F, H);
        
        int wid = 0;
        int hei = 0;
        if (x1.start <= x2.start) {
            if (x1.end > x2.start) {
                wid = Math.min(x1.end, x2.end) - Math.max(x2.start, x1.start);
            }
        } else {
            if (x2.end > x1.start) {
                wid = Math.min(x2.end, x1.end) - Math.max(x1.start, x2.start);
            }
        }
        
        if (y1.start <= y2.start) {
            if (y1.end > y2.start) {
                hei = Math.min(y1.end, y2.end) - Math.max(y2.start, y1.start);
            }
        } else {
            if (y2.end > y1.start) {
                hei = Math.min(y2.end, y1.end) - Math.max(y1.start, y2.start);
            }
        }
        
        return area1 + area2 - wid * hei;
    }
}

###Points

简单计算几何。根据容斥原理：S(M ∪ N) = S(M) + S(N) - S(M ∩ N) 题目可以转化为计算矩形相交部分的面积 S(M) = (C - A) * (D - B) S(N) = (G - E) * (H - F) S(M ∩ N) = max(min(C, G) - max(A, E), 0) * max(min(D, H) - max(B, F), 0)

Related Posts