C++ এ নিখুঁত আয়তক্ষেত্র

ধরুন আমাদের কাছে 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-এর জন্য re −

  • 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] concatenate r[3]

  • s4 :=r[2] concatenate 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