इस ट्यूटोरियल में, हम एक प्रोग्राम लिखने जा रहे हैं जो एक लाइन के सेगमेंट्स के मिलन की लंबाई का पता लगाता है।
हमें लाइन सेगमेंट के शुरुआती और अंतिम बिंदु दिए गए हैं और हमें लाइन के सेगमेंट के मिलन की लंबाई खोजने की जरूरत है।
हम जिस एल्गोरिथम का उपयोग करने जा रहे हैं उसे क्ली का एल्गोरिथम कहा जाता है।
आइए समस्या को हल करने के लिए चरणों को देखें।
- सभी खंडों के निर्देशांक के साथ सरणी प्रारंभ करें।
- एक वेक्टर को इनिशियलाइज़ करें, जिसे पॉइंट्स कहा जाता है, जिसका आकार सेगमेंट एरे से दोगुना है।
- सेगमेंट सरणी पर पुनरावृति करें।
- इंडेक्स i * 2 पर पॉइंट ऐरे के मानों को मौजूदा सेगमेंट के पहले पॉइंट से भरें और असत्य।
- इंडेक्स i * 2 + 1 पर पॉइंट ऐरे के मानों को मौजूदा सेगमेंट के दूसरे पॉइंट से भरें और असत्य।
- अंक सरणी को क्रमबद्ध करें।
- एक काउंटर चर के साथ अंक सरणी पर पुनरावृति।
- यदि काउंटर 0 से बड़ा है, तो परिणाम में 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
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उनका टिप्पणी अनुभाग में उल्लेख करें।