এই টিউটোরিয়ালে, আমরা একটি প্রোগ্রাম লিখব যা লাইন সেগমেন্টের ইউনিয়নের দৈর্ঘ্য বের করবে।
আমাদের লাইন সেগমেন্টের শুরু এবং শেষ পয়েন্ট দেওয়া আছে এবং আমাদের লাইন সেগমেন্টের ইউনিয়নের দৈর্ঘ্য বের করতে হবে।
এই কাজের জন্য আমরা ক্লির অ্যালগরিদম (Klee's Algorithm) ব্যবহার করব।
সমস্যা সমাধানের ধাপসমূহ
- সকল সেগমেন্টের কোঅর্ডিনেটস দিয়ে অ্যারে ইনিশিয়ালাইজ করুন।
- সেগমেন্ট অ্যারেতের আকারের দ্বিগুণ সাইজের একটি পয়েন্টস (points) ভেক্টর ইনিশিয়ালাইজ করুন।
- সেগমেন্ট অ্যারেটি parcour করুন।
- পয়েন্টস অ্যারেতে i*2 ইনডেক্সে বর্তমান সেগমেন্টের প্রথম পয়েন্ট এবং false সংরক্ষণ করুন।
- পয়েন্টস অ্যারেতে i*2+1 ইনডেক্সে বর্তমান সেগমেন্টের দ্বিতীয় পয়েন্ট এবং true সংরক্ষণ করুন।
- পয়েন্টস অ্যারেটি সর্ট করুন।
- একটি কাউন্টার ভেরিয়েবল সহ পয়েন্টস অ্যারেটি parcour করুন।
- যদি কাউন্টার ০-এর চেয়ে বড় হয়, তবে i এবং i-1 তম পয়েন্টের পার্থক্য ফলাফলে যোগ করুন।
- যদি দ্বিতীয় পয়েন্ট হয় তবে কাউন্টার ডিক্রিমেন্ট করুন, অন্যথায় ইনক্রিমেন্ট করুন।
- ফলাফল রিটার্ন করুন।
উদাহরণ কোড
#include<bits/stdc++.h>
using namespace std;
int segmentUnionLength(const vector<pair <int,int>> &segments) {
int n = segments.size();
vector<pair<int, bool>> points(n * 2);
for (int i = 0; i < n; i++) {
points[i*2] = make_pair(segments[i].first, false);
points[i*2 + 1] = make_pair(segments[i].second, true);
}
sort(points.begin(), points.end());
int result = 0, count = 0;
for (int i = 0; i < n * 2; i++){
if (count) {
result += points[i].first - points[i-1].first;
}
points[i].second ? count-- : count++;
}
return result;
}
int main() {
vector<pair<int,int>> segments;
segments.push_back(make_pair(1, 3));
segments.push_back(make_pair(2, 7));
segments.push_back(make_pair(6, 12));
segments.push_back(make_pair(13, 5));
cout << segmentUnionLength(segments) << endl;
return 0;
}
আউটপুট
উপরের কোডটি রান করলে নিচের ফলাফল পাওয়া যাবে:
6
নিষ্কর্ষ
এই টিউটোরিয়াল সম্পর্কে আপনার যেকোনো প্রশ্ন থাকলে কমেন্ট সেকশনে জানাতে পারেন।
