Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में डिवाइड एंड कंकर एल्गोरिदम का उपयोग करके कन्वेक्स हल


इस ट्यूटोरियल में, हम दी गई बिंदुओं के सेट का कन्वेक्स हल ढूंढने के लिए एक प्रोग्राम पर चर्चा करेंगे।

कन्वेक्स हल सबसे छोटा बहुभुज उत्तल आकृति है जो सभी दिए गए बिंदुओं को या तो सीमा पर या आकृति के अंदर समाहित करता है।

इस प्रोग्राम में, हम दिए गए बिंदुओं को छोटे खंडों में विभाजित करने के लिए ब्रूट फोर्स का उपयोग करेंगे और फिर अंत में उनको मर्ज करेंगे जो कन्वेक्स हल बनाने के लिए अनुसरण करते हैं।

उदाहरण

#include<bits/stdc++.h> using namespace std; //बहुभुज के केंद्र बिंदु को संग्रहीत करना pair<int, int> mid; //एक विशेष बिंदु का चतुर्थांश गणना int quad(pair<int, int> p){    if (p.first >= 0 && p.second >= 0)    return 1;    if (p.first <= 0 && p.second >= 0)    return 2;    if (p.first <= 0 && p.second <= 0)    return 3;    return 4; } //यदि रेखा बहुभुज को छू रही है int calc_line(pair<int, int> a, pair<int, int> b, pair<int, int> c){    int res = (b.second-a.second)*(c.first-b.first) -    (c.second-b.second)*(b.first-a.first);    if (res == 0)    return 0;    if (res > 0)    return 1;    return -1; } //सॉर्टिंग के लिए तुलना फ़ंक्शन bool compare(pair<int, int> p1, pair<int, int> q1){    pair<int, int> p = make_pair(p1.first - mid.first,    p1.second - mid.second);    pair<int, int> q = make_pair(q1.first - mid.first,    q1.second - mid.second);    int one = quad(p);    int two = quad(q);    if (one != two)    return (one < two);    return (p.second*q.first < q.second*p.first); } //दोनों बहुभुजों के लिए ऊपरी स्पर्शरेखा ढूंढना vector<pair<int, int>> merger(vector<pair<int, int> > a, vector<pair<int, int> > b){    int n1 = a.size(), n2 = b.size();    int ia = 0, ib = 0;    for (int i=1; i<n1; i++)    if (a[i].first > a[ia].first)    ia = i;    //b का सबसे बाएं बिंदु गणना    for (int i=1; i<n2; i++)    if (b[i].first < b[ib].first)    ib=i;    int inda = ia, indb = ib;    bool done = 0;    while (!done){       done = 1;       while (calc_line(b[indb], a[inda], a[(inda+1)%n1]) >=0)       inda = (inda + 1) % n1;       while (calc_line(a[inda], b[indb], b[(n2+indb-1)%n2]) <=0){          indb = (n2+indb-1)%n2;          done = 0;       }    }    int uppera = inda, upperb = indb;    inda = ia, indb=ib;    done = 0;    int g = 0;    //निचली स्पर्शरेखा की गणना    while (!done){       done = 1;       while (calc_line(a[inda], b[indb], b[(indb+1)%n2])>=0)       indb=(indb+1)%n2;       while (calc_line(b[indb], a[inda], a[(n1+inda-1)%n1])<=0){       inda=(n1+inda-1)%n1;       done=0;    } } int lowera = inda, lowerb = indb; vector<pair<int, int>> ret; //कन्वेक्स हल प्राप्त करने के लिए दो बहुभुजों को मर्ज करना int ind = uppera; ret.push_back(a[uppera]); while (ind != lowera){    ind = (ind+1)%n1;    ret.push_back(a[ind]); } ind = lowerb; ret.push_back(b[lowerb]); while (ind != upperb){    ind = (ind+1)%n2;    ret.push_back(b[ind]); } return ret; } //कन्वेक्स हल ढूंढने के लिए ब्रूट फोर्स एल्गोरिदम vector<pair<int, int>> bruteHull(vector<pair<int, int>> a){    set<pair<int, int> >s;    for (int i=0; i<a.size(); i++){       for (int j=i+1; j<a.size(); j++){          int x1 = a[i].first, x2 = a[j].first;          int y1 = a[i].second, y2 = a[j].second;          int a1 = y1-y2;          int b1 = x2-x1;          int c1 = x1*y2-y1*x2;          int pos = 0, neg = 0;          for (int k=0; k<a.size(); k++){             if (a1*a[k].first+b1*a[k].second+c1 <= 0)             neg++;             if (a1*a[k].first+b1*a[k].second+c1 >= 0)             pos++;          }          if (pos == a.size() || neg == a.size()){             s.insert(a[i]);             s.insert(a[j]);          }       }    }    vector<pair<int, int>>ret;    for (auto e:s)    ret.push_back(e);    //वामावर्त दिशा में आगे बढ़ना    mid = {0, 0};    int n = ret.size();    for (int i=0; i<n; i++){       mid.first += ret[i].first;       mid.second += ret[i].second;       ret[i].first *= n;       ret[i].second *= n;    }    sort(ret.begin(), ret.end(), compare);    for (int i=0; i<n; i++)    ret[i] = make_pair(ret[i].first/n, ret[i].second/n);    return ret; } //कन्वेक्स हल का मान लौटाना vector<pair<int, int>> divide(vector<pair<int, int>> a){    if (a.size() <= 5)    return bruteHull(a);    // left में बाएं आधे बिंदु हैं    // right में दाएं आधे बिंदु हैं    vector<pair<int, int>>left, right;    for (int i=0; i<a.size()/2; i++)    left.push_back(a[i]);    for (int i=a.size()/2; i<a.size(); i++)    right.push_back(a[i]);    vector<pair<int, int>>left_hull = divide(left);    vector<pair<int, int>>right_hull = divide(right);    //कन्वेक्स हल्स को मर्ज करना    return merger(left_hull, right_hull); } int main(){    vector<pair<int, int> > a;    a.push_back(make_pair(0, 0));    a.push_back(make_pair(1, -4));    a.push_back(make_pair(-1, -5));    a.push_back(make_pair(-5, -3));    a.push_back(make_pair(-3, -1));    a.push_back(make_pair(-1, -3));    a.push_back(make_pair(-2, -2));    a.push_back(make_pair(-1, -1));    a.push_back(make_pair(-2, -1));    a.push_back(make_pair(-1, 1));    int n = a.size();    sort(a.begin(), a.end());    vector<pair<int, int> >ans = divide(a);    cout << "Convex Hull:\n";    for (auto e:ans)    cout << e.first << " "<< e.second << endl;    return 0; }

आउटपुट

Convex Hull: -5 -3 -1 -5 1 -4 0 0 -1 1

  1. - C++ का उपयोग करके "ग्रेटर दैन" और "नॉट लेस दैन" के लिए क्वेरी

    इस लेख में, हमें एक समस्या दी गई है, हमें एक एरे दिया गया है, और दो प्रकार की क्वेरी हैं जिनका हमें उत्तर देना है। टाइप 0 - हमें x (दिए गए मान) से अधिक या बराबर तत्वों की संख्या की गणना करनी है। टाइप 1 - हमें x (दिए गए मान) से सख्ती से अधिक तत्वों की संख्या की गणना करनी है। यहाँ एक सरल उद

  1. OpenCV में C++ का उपयोग करके आंख की पुतली की गति का पता लगाएं और ट्रैक करें OpenCV में C++ का उपयोग करके आंख की पुतली की गति का पता लगाएं और ट्रैक करें

    यहाँ, हम सीखेंगे कि OpenCV में आंख की पुतली की गति का पता कैसे लगाएं और उसे ट्रैक कैसे करें।निम्नलिखित प्रोग्राम आंख की पुतली का पता लगाने और स्थान को ट्रैक करने को दर्शाता है।उदाहरण#include<iostream> #include<opencv2/core/core.hpp> #include<opencv2/highgui/highgui.hpp> #include<

  1. C++ में वृत्त और आयत के ओवरलैप की जांच C++ में वृत्त और आयत के ओवरलैप की जांच

    मान लीजिए हमारे पास एक वृत्त है जिसे (त्रिज्या, xc, yc) से दर्शाया जाता है, जहां (xc, yc) केंद्र के निर्देशांक हैं। हमारे पास एक अक्ष-संरेखित आयत भी है जिसे (x1, y1, x2, y2) से दर्शाया जाता है, जहां (x1, y1) निचले-बाएं कोने के निर्देशांक हैं और (x2, y2) ऊपरी-दाएं कोने के निर्देशांक हैं। हमें जांचना