สี่เหลี่ยมผืนผ้าที่สมบูรณ์แบบใน 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] ต่อ r[1]

  • s2 :=r[0] ต่อ 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 ใช้เนมสเปซ std;class Solution {public:bool isRectangleCover(vector> &re) { unordered_set visit; พื้นที่ int =0; int x2 =INT_MIN; int x1 =INT_MAX; int y2 =INT_MIN; int y1 =INT_MAX; สำหรับ (อัตโนมัติ &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 =to_string(r[0]) + to_string(r[1]); สตริง s2 =to_string(r[0]) + to_string(r[3]); สตริง s3 =to_string(r[2]) + to_string(r[3]); สตริง s4 =to_string(r[2]) + to_string(r[1]); ถ้า (visited.count(s1)) { visit.erase(s1); } อื่นมาที่ visit.insert(s1); ถ้า (visited.count(s2)) { visit.erase(s2); } อื่นมาที่ visit.insert(s2); ถ้า (visited.count(s3)) { visit.erase(s3); } อื่นมาที่ visit.insert(s3); ถ้า (visited.count (s4)) { visit.erase (s4); } อื่นมาที่ visit.insert(s4); } string s1 =to_string(x1) + to_string(y1); สตริง s2 =to_string(x2) + to_string(y1); สตริง s3 =to_string(x1) + to_string(y2); สตริง s4 =to_string(x2) + to_string(y2); if (!visited.count(s1) || !visited.count(s2) || !visited.count(s3) || !visited.count(s4) || visit.size() !=4) คืนค่าเท็จ พื้นที่ส่งคืน ==(x2 - x1) * (y2 - y1); }};main() { โซลูชัน ob; เวกเตอร์<เวกเตอร์> v ={{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}}; ศาล <<(ob.isRectangleCover(v));}

อินพุต

ผลลัพธ์

1