Hình chữ nhật hoàn hảo trong C ++

Giả sử chúng ta có N hình chữ nhật thẳng hàng với trục, chúng ta phải kiểm tra xem tất cả chúng có cùng nhau tạo thành một bìa chính xác của một vùng hình chữ nhật hay không. Ở đây mỗi hình chữ nhật được biểu diễn dưới dạng điểm dưới cùng bên trái và điểm trên cùng bên phải. Vì vậy, một hình vuông đơn vị được biểu diễn là [1,1,2,2]. (điểm dưới cùng bên trái là (1, 1) và điểm trên cùng bên phải là (2, 2)).

Vì vậy, nếu đầu vào giống như hình chữ nhật =[[1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4]], thì kết quả đầu ra sẽ đúng vì tất cả 5 hình chữ nhật cùng nhau tạo thành một bìa chính xác của một vùng hình chữ nhật.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một tập hợp đã truy cập
khu vực:=0
x2:=-inf, x1:=inf
y2:=-inf, y1:=inf
cho mỗi r trong danh sách đã cho lại -
- x1:=tối thiểu của r [0] và x1
- x2:=tối đa của r [2] và x2
- y1:=tối thiểu của r [1] và y1
- y2:=tối đa của r [3] và y2
- area:=area + ((r [2] - r [0]) * (r [3] - r [1]))
- s1:=r [0] nối r [1]
- s2:=r [0] nối r [3]
- s3:=r [2] nối r [3]
- s4:=r [2] nối r [1]
- nếu s1 được truy cập, thì -
  - xóa s1 khỏi đã truy cập
- Nếu không
  - chèn s1 vào đã truy cập
- nếu s2 được truy cập, thì -
  - xóa s2 khỏi đã truy cập
- Nếu không
  - chèn s2 vào đã truy cập
- nếu s3 được truy cập, thì -
  - xóa s3 khỏi đã truy cập
- Nếu không
  - chèn s3 vào đã truy cập
- nếu s4 được truy cập, thì -
  - xóa s4 khỏi đã truy cập
- Nếu không
  - chèn s4 vào đã truy cập
s1:=nối x1 và y1
s2:=nối x2 và y1
s3:=nối x1 và y2
s4:=nối x2 và y2
nếu tất cả s1, s2, s3, s4 đều không được truy cập thì
- trả về false
trả về true khi diện tích giống như ((x2 - x1) * (y2 - y1))

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

{{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}}

Hình chữ nhật hoàn hảo trong C ++

Ví dụ

Đầu vào

Đầu ra