सी++ में बिल्कुल सही आयत

मान लीजिए कि हमारे पास N अक्ष-संरेखित आयत हैं, हमें यह जांचना है कि वे सभी मिलकर एक आयताकार क्षेत्र का एक सटीक आवरण बनाते हैं या नहीं। यहां प्रत्येक आयत को नीचे-बाएं बिंदु और शीर्ष-दाएं बिंदु के रूप में दर्शाया गया है। तो एक इकाई वर्ग को [1,1,2,2] के रूप में दर्शाया जाता है। (निचला-बाएं बिंदु (1, 1) है और शीर्ष-दाएं बिंदु (2, 2)) है।

तो, अगर इनपुट आयतों की तरह है =[[1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4]], तो आउटपुट सही होगा क्योंकि सभी 5 आयत एक साथ एक आयताकार क्षेत्र का एक सटीक आवरण बनाते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• देखे गए एक सेट को परिभाषित करें

• क्षेत्र :=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

  • क्षेत्र :=क्षेत्र + ((r[2] - r[0]) * (r[3] - r[1]))

  • s1 :=r[0] concatenate r[1]

  • s2 :=r[0] concatenate r[3]

  • s3 :=r[2] कॉनटेननेट r[3]

  • s4 :=r[2] कॉनटेननेट r[1]

  • यदि s1 का दौरा किया जाता है, तो -

    • विज़िट किए गए से s1 हटाएं

  • अन्यथा

    • विज़िट किए गए में s1 डालें

  • यदि s2 का दौरा किया जाता है, तो -

    • विज़िट किए गए से s2 हटाएं

  • अन्यथा

    • विज़िट किए गए में s2 डालें

  • यदि s3 का दौरा किया जाता है, तो -

    • विज़िट किए गए से s3 हटाएं

  • अन्यथा

    • विज़िट किए गए में s3 डालें

  • यदि s4 का दौरा किया जाता है, तो -

    • देखे गए से s4 हटाएं

  • अन्यथा

    • विज़िट किए गए में s4 डालें

• s1 :=x1 और y1 को संयोजित करें

• s2 :=x2 और y1 को संयोजित करें

• s3 :=x1 और y2 को संयोजित करें

• s4:=x2 और y2 को संयोजित करें

• अगर s1, s2, s3, s4 सभी का दौरा नहीं किया जाता है, तो

  • झूठी वापसी

• जब क्षेत्रफल समान हो ((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