สี่เหลี่ยมผืนผ้าแบบสมบูรณ์ใน C++

สมมติว่าเรามีสี่เหลี่ยมผืนผ้าที่จัดเรียงตามแกน 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,x2,y1,y2 เป็นขอบเขตโดยรวม; area += (r[2]-r[0])*(r[3]-r[1]); สร้างสตริงมุม 4 จุด s1..s4; ถ้ามุมอยู่ใน visited ให้ลบออก มิฉะนั้นใส่เข้าไป
• หลังลูป สร้างสตริงมุม 4 จุดของสี่เหลี่ยมใหญ่ s1..s4; ถ้ามุมทั้ง 4 ไม่อยู่ใน visited หรือ visited.size() != 4 คืนค่า false
• คืนค่า true ถ้า area == (x2-x1)*(y2-y1)

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isRectangleCover(vector>& re) {
        unordered_set visited;
        int area = 0;
        int x2 = INT_MIN, x1 = INT_MAX, y2 = INT_MIN, 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> 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