Short C++ Sweep Line


  • 0
    B
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            vector<vector<int>> edges;
            int minx=INT_MAX, miny=INT_MAX, maxx=INT_MIN, maxy=INT_MIN;
            int sum = 0;
            for(auto &a:rectangles) {
                edges.push_back({a[0],1,a[1],a[3]});
                edges.push_back({a[2],-1,a[1],a[3]});
                sum+=(a[2]-a[0])*(a[3]-a[1]);
                minx = min(minx, a[0]);
                maxx = max(maxx, a[2]);
                miny = min(miny, a[1]);
                maxy = max(maxy, a[3]);
            }
            sort(edges.begin(), edges.end());
            set<pair<int,int>> st;
            for(auto &a:edges) {
                if(a[1]<0) st.erase({a[2],a[3]});
                else {
                    auto it = st.lower_bound({a[2],a[3]});
                    if(it!=st.end() && it->first<a[3]) return false;
                    if(it!=st.begin() && (--it)->second>a[2]) return false;
                    st.insert({a[2],a[3]});
                }
            }
            return sum==(maxy-miny)*(maxx-minx);
        }
    

  • 0
    E

    @buaaroger said in Short C++ Sweep Line:

        bool isRectangleCover(vector<vector<int>>& rectangles) {
            vector<vector<int>> edges;
            int minx=INT_MAX, miny=INT_MAX, maxx=INT_MIN, maxy=INT_MIN;
            int sum = 0;
            for(auto &a:rectangles) {
                edges.push_back({a[0],1,a[1],a[3]});
                edges.push_back({a[2],-1,a[1],a[3]});
                sum+=(a[2]-a[0])*(a[3]-a[1]);
                minx = min(minx, a[0]);
                maxx = max(maxx, a[2]);
                miny = min(miny, a[1]);
                maxy = max(maxy, a[3]);
            }
            sort(edges.begin(), edges.end());
            set<pair<int,int>> st;
            for(auto &a:edges) {
                if(a[1]<0) st.erase({a[2],a[3]});
                else {
                    auto it = st.lower_bound({a[2],a[3]});
                    if(it!=st.end() && it->first<a[3]) return false;
                    if(it!=st.begin() && (--it)->second>a[2]) return false;
                    st.insert({a[2],a[3]});
                }
            }
            return sum==(maxy-miny)*(maxx-minx);
        }
    

    can you explain what this code is doing?

    why are 1 and -1 being pushed as coordinates in the following?

    edges.push_back({a[0],1,a[1],a[3]});
    edges.push_back({a[2],-1,a[1],a[3]});


Log in to reply
 

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