मान लीजिए कि हमारे पास (अक्ष-संरेखित) आयतों की एक सूची है। यहाँ प्रत्येक आयत [i] ={x1, y1, x2, y2}, जहाँ (x1, y1) निचले-बाएँ कोने का बिंदु है, और (x2, y2) ऊपरी-दाएँ कोने के बिंदु हैं आयत।
हमें समतल में सभी आयतों द्वारा कवर किया गया कुल क्षेत्रफल ज्ञात करना है। उत्तर बहुत हो सकता है, इसलिए हम मॉड्यूल 10^9 + 7 का उपयोग कर सकते हैं।
तो, अगर इनपुट पसंद है
तो आउटपुट 6 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
मी =10^9 + 7
-
फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,
. लगेगा -
वापसी ((एक मॉड एम) + (बी मॉड एम) मॉड एम)
-
एक फ़ंक्शन को परिभाषित करें संपीड़ित इसमें 2d मैट्रिक्स v
. लगेगा -
एक सरणी अस्थायी परिभाषित करें
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
अस्थायी के अंत में v[i, 0] डालें
-
अस्थायी के अंत में v[i, 2] डालें
-
-
सरणी अस्थायी क्रमबद्ध करें
-
एक नक्शा परिभाषित करें, फिर से देखें
-
आईडीएक्स:=0
-
प्रारंभ करने के लिए मैं:=0, जब मैं <अस्थायी का आकार, अद्यतन (मैं 1 से बढ़ाएँ), करते हैं
-
अगर अस्थायी [i] रिट का सदस्य नहीं है, तो -
-
ret[temp[i]] :=idx
-
(आईडीएक्स को 1 से बढ़ाएं)
-
-
-
वापसी रिट
-
मुख्य विधि से निम्न कार्य करें -
-
सरणी xv परिभाषित करें
-
xv के अंत में { 0 } डालें
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
xv के अंत में v[i, 0] डालें
-
xv के अंत में v[i, 2] डालें
-
-
सरणी xv को सॉर्ट करें
-
uniItr =xv के अद्वितीय तत्वों वाली सूची का पहला तत्व
-
xv से uniItr हटाएं
-
एक मानचित्र अनुक्रमणिका परिभाषित करें
-
आईडीएक्स:=0
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
अनुक्रमणिका [xv [i]] :=i
-
-
इंडेक्स आकार के समान आकार की एक सरणी गणना परिभाषित करें
-
एक 2D सरणी x परिभाषित करें
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
x1 :=v[i, 0], y1 :=v[i, 1]
-
x2 :=v[i, 2], y2 :=v[i, 3]
-
x के अंत में { y1, x1, x2, 1 } डालें
-
x के अंत में {y2, x1, x2, -1} डालें
-
-
सरणी x को सॉर्ट करें
-
रिट:=0
-
योग :=0, वर्तमानY :=0
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
वाई:=एक्स[i, 0]
-
x1 :=x[i, 1], x2 :=x[i, 2]
-
सिग :=x[i, 3]
-
रिट:=जोड़ें (रिट, (y - currentY) * योग)
-
वर्तमान वाई:=वाई
-
इनिशियलाइज़ करने के लिए मैं :=index[x1], जब i
-
गिनती[i] :=गिनती[i] + sig
-
-
योग :=0
-
प्रारंभ करने के लिए i:=0, जब i <गिनती का आकार, अद्यतन (i से 1 तक बढ़ाएं), करते हैं -
-
अगर गिनती [i]> 0, तो
-
योग :=योग + (xv[i + 1] - xv[i])
-
-
-
-
रिटर्न रिट मॉड एम
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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;
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());
vector<int>::iterator 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;
int x1, x2, y1, y2;
for (int i = 0; i < v.size(); i++) {
x1 = v[i][0];
y1 = v[i][1];
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];
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;
}
};
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}} आउटपुट
6