C++ में दी गई लाइन सेगमेंट लंबाई से अधिकतम समानांतर चतुर्भुज की संख्या

दिया गया कार्य दिए गए N लाइन सेगमेंट का उपयोग करके बनाए जा सकने वाले अधिकतम समानांतर चतुर्भुज की संख्या ढूंढना है यदि प्रत्येक लाइन सेगमेंट का उपयोग अधिकतम एक समानांतर चतुर्भुज में किया जा सकता है।

उदाहरण से समझते हैं

इनपुट - Arr[] = {8, 3, 1, 3, 8, 7, 1, 3, 5, 3}

आउटपुट - 2

व्याख्या - उपरोक्त दिए गए लाइन सेगमेंट से, बनने वाले दो समानांतर चतुर्भुज भुजाओं 8, 1, 8, 1 और 3, 3, 3, 3 के साथ हैं।

इनपुट - Arr[] = {7, 9, 9, 7}

आउटपुट - 1

प्रयुक्त दृष्टिकोण

बनाए जा सकने वाले अधिकतम समानांतर चतुर्भुज = 4 समान भुजाओं वाले समानांतर चतुर्भुज + 2 समान भुजाओं वाले समानांतर चतुर्भुज।
MaxParr() फंक्शन में, L = Arr[0] नामक एक वेरिएबल आरंभ करें जिसे फ्रीक्वेंसी स्टोर करने के लिए उपयोग किए जाने वाले ऐरे के आकार के रूप में उपयोग किया जाएगा।
i=1 से i<N तक लूप चलाएं और चेक करें यदि (Arr[i] > L), और if स्टेटमेंट के अंदर L=Arr[i] रखें। लूप के बाहर L का आकार 1 से बढ़ाएं।
फिर फ्रीक्वेंसी ऐरे आरंभ करें int Freq[L] = {0}। i=0 से i<N तक लूप चलाएं और प्रत्येक सेगमेंट की घटना को 1 से बढ़ाएं।
count = 0 टाइप का int आरंभ करें अंतिम समानांतर चतुर्भुज की गिनती स्टोर करने के लिए।
i=0 से i<L तक लूप चलाएं और 4 समान भुजाओं वाले समानांतर चतुर्भुज के लिए चेक करें और यदि मिले तो count का मान तदनुसार बढ़ाएं।
left=0 टाइप का int आरंभ करें 2 समान भुजाओं का उपयोग करके बनाए जा सकने वाले समानांतर चतुर्भुज की संख्या स्टोर करने के लिए।
अंत में i=0 से i<L तक लूप चलाएं और चेक करें यदि (Freq[i] >= 2) और यदि हां तो left में 1 जोड़ें।
count += left/2 रखें और count वापस करें।

C++ प्रोग्राम उदाहरण

#include <bits/stdc++.h>
using namespace std;

int MaxParr(int N, int Arr[]) {
    // फ्रीक्वेंसी ऐरे की लंबाई ढूंढना
    int L = Arr[0];
    for (int i = 1; i < N; i++) {
        if (Arr[i] > L)
            L = Arr[i];
    }
    L = L + 1;
    int Freq[L] = {0};
    for (int i = 0; i < N; i++) {
        // प्रत्येक लाइन सेगमेंट की घटना बढ़ाना
        Freq[Arr[i]] += 1;
    }
    
    // समानांतर चतुर्भुज की संख्या स्टोर करने के लिए
    int count = 0;
    for (int i = 0; i < L; i++) {
        /* 4 समान भुजाओं का उपयोग करके बनाए जा सकने वाले समानांतर चतुर्भुज */
        count += int(Freq[i] / 4);
        Freq[i] = Freq[i] % 4;
    }
    
    int left = 0;
    for (int i = 0; i < L; i++) {
        // 2 या अधिक घटनाओं वाले सेगमेंट गिनना
        if (Freq[i] >= 2)
            left += 1;
    }
    
    /* 2 समान भुजाओं का उपयोग करके बनाए जा सकने वाले समानांतर चतुर्भुज को अंतिम गिनती में जोड़ना */
    count += left / 2;
    return count;
}

int main() {
    int N = 10;
    int Arr[] = { 8, 3, 1, 3, 8, 7, 1, 3, 5, 3 };
    cout << MaxParr(N, Arr);
}