Clear solution by finding overlapped length on x/y


  • 0
    L

    In general we just need to find out the overlapped rect area (if it exists), so we need to find out the overlapped length on x and y directions.

    1. check the 2 rects and find which one is on the left, name it r1 (the one on the right is r2)
    2. now check the right boundary. there are only 2 possibilities: r2 is within r1 (on x axis only) or r2/r1 is overlapping. Then we can get the overlapped length on x
    3. do similar actions for y directions to find the overlapped length on y

    result = r1.size() + r2.size() - overlapped_x*overlapped_y;

    The key point is when we check for x-axis, forget about y, and vice versa.

    class Solution {
        struct Rect {
            int x1;
            int y1;
            int x2;
            int y2;
            int size() {
                return (x2-x1)*(y2-y1);
            }
            Rect(int a,int b,int c, int d):x1(a),y1(b),x2(c),y2(d) {}
        };
        
    public:
        int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
            Rect r1(A,B,C,D);
            Rect r2(E,F,G,H);
            if (A>E) {
                Rect temp = r2;
                r2=r1;
                r1=temp;
            }
            
            if (r1.x2 > r2.x1) {
                int ox = r2.x2 < r1.x2 ? (r2.x2-r2.x1) : (r1.x2-r2.x1);  //overlapped x
                
                if (r1.y1 > r2.y1) {
                    Rect temp = r1;
                    r1 = r2;
                    r2 = temp;
                }
                // r1 is lower
                if (r1.y2 > r2.y1) {
                    int oy = r2.y2 < r1.y2 ? (r2.y2 - r2.y1) : (r1.y2 - r2.y1);
                    return r1.size()+r2.size() - ox*oy;
                }
            }
            
            return r1.size() + r2.size();
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.