C++-এ আয়তাকার এলাকা II (Rectangle Area II) সমাধান

ধরুন আমাদের একটি অক্ষ-সমান্তরাল (axis-aligned) আয়তের তালিকা দেওয়া আছে। প্রতিটি আয়ত rectangle[i] = {x1, y1, x2, y2} ফরম্যাটে দেওয়া থাকে, যেখানে (x1, y1) হল নীচের বাম কোণার বিন্দু এবং (x2, y2) হল উপরের ডান কোণার বিন্দু।

আমাদের কাজ হল সমতলে সকল আয়ত দ্বারা আচ্ছাদিত মোট এলাকা বের করা। উত্তরটি বড় হতে পারে, তাই আমরা মডুলো 10^9 + 7 ব্যবহার করব।

উদাহরণ

উপরের চিত্রের জন্য আউটপুট হবে 6।

সমাধানের ধাপসমূহ

m = 10^9 + 7 ধ্রুবক সেট করুন।
add() ফাংশন তৈরি করুন যা ((a % m) + (b % m)) % m রিটার্ন করে।
compress() ফাংশন তৈরি করুন যা 2D ম্যাট্রিক্স নেয় এবং কোঅর্ডিনেট কম্প্রেশন করে।
মূল মেথড থেকে:
- xv অ্যারে তৈরি করুন এবং সকল আয়তের x-কোঅর্ডিনেট সংগ্রহ করুন।
- xv সর্ট করে ডুপ্লিকেট সরান।
- প্রতিটি x-কোঅর্ডিনেটের জন্য ইন্ডেক্স ম্যাপ তৈরি করুন।
- সইপ লাইন অ্যালগরিদম (sweep line algorithm) ব্যবহার করে এলাকা গণনা করুন।

প্রোগ্রাম উদাহরণ

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

class Solution {
public:
    lli add(lli a, lli b) {
        return ((a % m) + (b % m)) % m;
    }
    
    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());
        auto uniItr = unique(xv.begin(), xv.end());
        xv.erase(uniItr, 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> > x;
        
        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];
            x.push_back({y1, x1, x2, 1});
            x.push_back({y2, x1, x2, -1});
        }
        sort(x.begin(), x.end());
        
        lli ret = 0;
        lli sum = 0, currentY = 0;
        
        for (int i = 0; i < x.size(); i++) {
            lli y = x[i][0];
            int x1 = x[i][1], x2 = x[i][2];
            int sig = x[i][3];
            
            ret = add(ret, (y - currentY) * sum);
            currentY = y;
            
            for (int i = index[x1]; i < index[x2]; i++) {
                count[i] += sig;
            }
            
            sum = 0;
            for (int i = 0; i < count.size(); i++) {
                if (count[i] > 0) {
                    sum += (xv[i + 1] - xv[i]);
                }
            }
        }
        return ret % m;
    }
};

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

ইনপুট

{{0,0,2,2},{1,0,2,3},{1,0,3,1}}