मान लीजिए हमारे पास N अक्ष-संरेखित आयत हैं, हमें जांचना होगा कि क्या वे सभी मिलकर एक आयताकार क्षेत्र का सटीक कवर बनाते हैं या नहीं। यहां प्रत्येक आयत को निचले-बाएं बिंदु और ऊपरी-दाएं बिंदु के रूप में दर्शाया गया है। तो एक यूनिट वर्ग को [1,1,2,2] के रूप में दर्शाया गया है। (निचला-बाएं बिंदु (1, 1) है और ऊपरी-दाएं बिंदु (2, 2) है)।
तो, यदि इनपुट rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] जैसा है, तो आउटपुट true होगा क्योंकि सभी 5 आयत मिलकर एक आयताकार क्षेत्र का सटीक कवर बनाते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
एक सेट visited परिभाषित करें
area := 0
x2 := -inf, x1 := inf
y2 := -inf, y1 := inf
दिए गए रेक्टेंगल्स की सूची में प्रत्येक r के लिए −
x1 := r[0] और x1 का न्यूनतम
x2 := r[2] और x2 का अधिकतम
y1 := r[1] और y1 का न्यूनतम
y2 := r[3] और y2 का अधिकतम
area := area + ((r[2] - r[0]) * (r[3] - r[1]))
s1 := r[0] को r[1] के साथ जोड़ें
s2 := r[0] को r[3] के साथ जोड़ें
s3 := r[2] को r[3] के साथ जोड़ें
s4 := r[2] को r[1] के साथ जोड़ें
यदि s1 visited में है, तो −
visited से s1 हटाएं
अन्यथा
visited में s1 डालें
यदि s2 visited में है, तो −
visited से s2 हटाएं
अन्यथा
visited में s2 डालें
यदि s3 visited में है, तो −
visited से s3 हटाएं
अन्यथा
visited में s3 डालें
यदि s4 visited में है, तो −
visited से s4 हटाएं
अन्यथा
visited में s4 डालें
s1 := x1 और y1 को जोड़ें
s2 := x2 और y1 को जोड़ें
s3 := x1 और y2 को जोड़ें
s4 := x2 और y2 को जोड़ें
यदि s1, s2, s3, s4 सभी visited में नहीं हैं, तो
false लौटाएं
true लौटाएं जब area, ((x2 - x1) * (y2 - y1)) के समान हो
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#include <bits/stdc++.h> using namespace std; class Solution { public: bool isRectangleCover(vector<vector<int>> &re) { unordered_set<string> visited; int area = 0; int x2 = INT_MIN; int x1 = INT_MAX; int y2 = INT_MIN; int y1 = INT_MAX; for (auto &r : re) { x1 = min(r[0], x1); x2 = max(r[2], x2); y1 = min(r[1], y1); y2 = max(r[3], y2); area += (r[2] - r[0]) * (r[3] - r[1]); string s1 = to_string(r[0]) + to_string(r[1]); string s2 = to_string(r[0]) + to_string(r[3]); string s3 = to_string(r[2]) + to_string(r[3]); string s4 = to_string(r[2]) + to_string(r[1]); if (visited.count(s1)) { visited.erase(s1); } else visited.insert(s1); if (visited.count(s2)) { visited.erase(s2); } else visited.insert(s2); if (visited.count(s3)) { visited.erase(s3); } else visited.insert(s3); if (visited.count(s4)) { visited.erase(s4); } else visited.insert(s4); } string s1 = to_string(x1) + to_string(y1); string s2 = to_string(x2) + to_string(y1); string s3 = to_string(x1) + to_string(y2); string s4 = to_string(x2) + to_string(y2); if (!visited.count(s1) || !visited.count(s2) || !visited.count(s3) || !visited.count(s4) || visited.size() != 4) return false; return area == (x2 - x1) * (y2 - y1); } }; main() { Solution ob; vector<vector<int>> v = {{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}}; cout << (ob.isRectangleCover(v)); }इनपुट
{{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}}आउटपुट
1
