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つの長方形すべてが一緒になって長方形領域の正確なカバーを形成するため、出力はtrueになります。

これを解決するには、次の手順に従います-

• 訪問した1セットを定義する

• 面積：=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の最大値

  • 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にアクセスすると、-

    • 訪問先からs1を削除

  • それ以外の場合

    • s1をvisitedに挿入します

  • 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がすべて訪問されていない場合は、

  • falseを返す

• 面積が（（x2-x1）*（y2-y1））と同じ場合はtrueを返します

例

理解を深めるために、次の実装を見てみましょう-

#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