当前位置:首页 » 编程语言

LeetCode:Rectangle Area

2015-11-22 17:18 本站整理 浏览(30)

Rectangle Area

Total Accepted: 23524 Total

Submissions: 84978 Difficulty: Easy

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.

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

思路:

两种情况:1)矩形相交;2)矩形不相交。

1)不相交:当A>=E或C<=E或B>=H或D<=H。

2)相交:求相交覆盖矩形的左下(x1,y2)、右上坐标(x2,y2):

x1 = max(A,E);y1 = max(B,F);

x2 = min(C,G);y2 = min(D,H);

所有的相交情况都符合上式。

code:

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int total = area(A,B,C,D)+area(E,F,G,H);
        if(A>=G || C<=E || B>=H || D<=F) {
            return total;
        }else{
            int x1=max(A,E);
            int y1=max(B,F);
            int x2=min(C,G);
            int y2=min(D,H);
            return total - area(x1,y1,x2,y2);
        }
    }
    int area(int x1,int y1, int x2, int y2) 
    {
         return abs((x1-x2)*(y2-y1));
    }
};