C++ में आयत क्षेत्रफल II (Rectangle Area II) - ओवरलैपिंग आयतों का कुल क्षेत्रफल

समस्या विवरण

हमें अक्ष-संरेखित (axis-aligned) आयतों की एक सूची दी गई है। प्रत्येक आयत rectangle[i] = {x1, y1, x2, y2} द्वारा दर्शाया गया है, जहां (x1, y1) निचले-बाएं कोने का बिंदु है और (x2, y2) ऊपरी-दाएं कोने का बिंदु है।

हमें तल (plane) में सभी आयतों द्वारा कवर किए गए कुल क्षेत्रफल को ज्ञात करना है। उत्तर बहुत बड़ा हो सकता है, इसलिए हम मॉड्यूलो 10^9 + 7 का उपयोग कर सकते हैं।

उदाहरण

इनपुट: {{0,0,2,2},{1,0,2,3},{1,0,3,1}}

आउटपुट: 6

समाधान दृष्टिकोण (स्वीप लाइन एल्गोरिदम)

यह समस्या स्वीप लाइन एल्गोरिदम और निर्देशांक संपीड़न (coordinate compression) का उपयोग करके हल की जाती है:

सभी अद्वितीय x-निर्देशांक एकत्र करें और उन्हें क्रमबद्ध करें।
प्रत्येक आयत के लिए दो घटनाएं (events) बनाएं: प्रवेश (y1, +1) और निकास (y2, -1)।
घटनाओं को y-निर्देशांक के अनुसार क्रमबद्ध करें।
स्वीप लाइन को y-अक्ष के साथ ऊपर ले जाएं, सक्रिय x- अंतराल की लंबाई बनाए रखें।
कुल क्षेत्रफल संचित करें: क्षेत्रफल += (वर्तमान_y - पिछला_y) * सक्रिय_लंबाई।

कार्यकारी प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;

class Solution {
public:
    lli add(lli a, lli b) {
        return ((a % MOD) + (b % MOD)) % MOD;
    }
    
    map<int, int> compress(vector<vector<int>>& v) {
        vector<int> temp;
        for (int i = 0; i < v.size(); i++) {
            temp.push_back(v[i][0]);
            temp.push_back(v[i][2]);
        }
        sort(temp.begin(), temp.end());
        map<int, int> ret;
        int idx = 0;
        for (int i = 0; i < temp.size(); i++) {
            if (!ret.count(temp[i])) {
                ret[temp[i]] = idx++;
            }
        }
        return ret;
    }
    
    int rectangleArea(vector<vector<int>>& v) {
        vector<int> xv;
        xv.push_back(0);
        for (int i = 0; i < v.size(); i++) {
            xv.push_back(v[i][0]);
            xv.push_back(v[i][2]);
        }
        sort(xv.begin(), xv.end());
        xv.erase(unique(xv.begin(), xv.end()), xv.end());
        
        map<int, int> index;
        int idx = 0;
        for (int i = 0; i < xv.size(); i++) {
            index[xv[i]] = i;
        }
        
        vector<int> count(index.size());
        vector<vector<int>> events;
        for (int i = 0; i < v.size(); i++) {
            int x1 = v[i][0], y1 = v[i][1];
            int x2 = v[i][2], y2 = v[i][3];
            events.push_back({y1, x1, x2, 1});
            events.push_back({y2, x1, x2, -1});
        }
        sort(events.begin(), events.end());
        
        lli ret = 0;
        lli sum = 0, currentY = 0;
        for (int i = 0; i < events.size(); i++) {
            lli y = events[i][0];
            int x1 = events[i][1], x2 = events[i][2];
            int sig = events[i][3];
            
            ret = add(ret, (y - currentY) * sum);
            currentY = y;
            
            for (int j = index[x1]; j < index[x2]; j++) {
                count[j] += sig;
            }
            
            sum = 0;
            for (int j = 0; j < count.size(); j++) {
                if (count[j] > 0) {
                    sum += (xv[j + 1] - xv[j]);
                }
            }
        }
        return ret % MOD;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,0,2,2},{1,0,2,3},{1,0,3,1}};
    cout << ob.rectangleArea(v);
    return 0;
}