ধরি আমাদের Nটি অ্যাক্সিস-আলাইনড (axis-aligned) রেক্ট্যাঙ্গেল আছে। আমাদের যাচাই করতে হবে কি সেগুলো মিলে একটি সম্পূর্ণ রেক্ট্যাঙ্গুলার অঞ্চল (rectangular region) তৈরি করে কিনা। প্রতিটি রেক্ট্যাঙ্গেল নিচের-বাম (bottom-left) এবং উপরের-ডান (top-right) পয়েন্ট দিয়ে প্রতিনিধিত্ব করা হয়। যেমন একটি ইউনিট স্কোয়ার হল [1,1,2,2] (bottom-left (1,1), top-right (2,2))।
উদাহরণস্বরূপ, rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] হলে আউটপুট হবে true কারণ এই ৫টি রেক্ট্যাঙ্গেল মিলে একটি সম্পূর্ণ রেক্ট্যাঙ্গুলার অঞ্চল তৈরি করে।
সমাধানের ধাপসমূহ
- একটি সেট
visitedসংজ্ঞায়িত। - area := 0
- x2 := -INF, x1 := INF
- y2 := -INF, y1 := INF
- প্রতিটি 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])
- s1 := r[0] + r[1] (স্ট্রিং ক্যাটেনেশন)
- s2 := r[0] + r[3]
- s3 := r[2] + r[3]
- s4 := r[2] + r[1]
- যদি s1 visited-এ থাকে: visited থেকে s1 ডিলিট, অন্যথায় ইনসার্ট।
- s2, s3, s4-র জন্যও একই কাজ।
- s1 := x1+y1, s2 := x2+y1, s3 := x1+y2, s4 := x2+y2 (স্ট্রিং ক্যাটেনেশন)
- যদি s1, s2, s3, s4 সব visited-এ না থাকে: false ফেরত।
- ফেরত: 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;
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);
}
};
int 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
