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

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


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

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

उदाहरण

#include <bits/stdc++.h> #define llu long long int using namespace std; //दिए गए बिंदु के लिए संरचना struct Point {    llu x, y;    bool operator<(Point p){    return x < p.x || (x == p.x && y < p.y);    } }; //स्व-निर्मित वेक्टर्स के क्रॉस प्रोडक्ट की गणना llu calc_crossproduct(Point O, Point A, Point B){    return (A.x - O.x) * (B.y - O.y)    - (A.y - O.y) * (B.x - O.x); } //सीमा पर बिंदुओं की गणना vector<Point> convex_hull(vector<Point> A){    int n = A.size(), k = 0;    if (n <= 3)    return A;    vector<Point> ans(2 * n);    //बिंदुओं को लेक्सिकोग्राफिकली सॉर्ट करना    sort(A.begin(), A.end());    for (int i = 0; i < n; ++i) {       while (k >= 2 && calc_crossproduct(ans[k - 2],       ans[k - 1], A[i]) <= 0)       k--;       ans[k++] = A[i];    }    //ऊपरी हल बनाना    for (size_t i = n - 1, t = k + 1; i > 0; --i) {       while (k >= t && calc_crossproduct(ans[k - 2],       ans[k - 1], A[i - 1]) <= 0)       k--;       ans[k++] = A[i - 1];    }    //दिए गए सरणी का आकार बदलना    ans.resize(k - 1);    return ans; } int main(){    vector<Point> points;    points.push_back({ 0, 3 });    points.push_back({ 2, 2 });    points.push_back({ 1, 1 });    points.push_back({ 2, 1 });    points.push_back({ 3, 0 });    points.push_back({ 0, 0 });    points.push_back({ 3, 3 });    vector<Point> ans = convex_hull(points);    for (int i = 0; i < ans.size(); i++)    cout << "(" << ans[i].x << ", "    << ans[i].y << ")" << endl;    return 0; }

आउटपुट

(0, 0) (3, 0) (3, 3) (0, 3)

  1. C/C++ में बर्कले का एल्गोरिथ्म C/C++ में बर्कले का एल्गोरिथ्म

    बर्कले का एल्गोरिथ्म वितरित प्रणालियों में क्लॉक सिंक्रोनाइज़ेशन के लिए उपयोग किया जाने वाला एक एल्गोरिथ्म है। यह एल्गोरिथ्म उन मामलों में उपयोग किया जाता है जब वितरित नेटवर्क के कुछ या सभी सिस्टम में निम्नलिखित समस्याएं होती हैं: A. मशीन के पास सटीक समय स्रोत नहीं है। B. नेटवर्क या मशीन के पास UTC

  1. C++ में बेलमैन-फोर्ड एल्गोरिदम C++ में बेलमैन-फोर्ड एल्गोरिदम

    बेलमैन-फोर्ड एल्गोरिदम एक डायनामिक प्रोग्रामिंग एल्गोरिदम है जिसका उपयोग किसी भी शीर्ष के सबसे छोटे पथ को खोजने के लिए किया जाता है जिसे एक शीर्ष से प्रारंभिक शीर्ष के रूप में माना जाता है। यह एल्गोरिदम पुनरावृत्त विधि का पालन करता है और लगातार सबसे छोटा पथ खोजने का प्रयास करता है। बेलमैन-फोर्ड एल्

  1. - C++ प्रोग्राम: ग्राहम स्कैन एल्गोरिदम से कन्वेक्स हल ढूंढना

    कन्वेक्स हल वह न्यूनतम बंद क्षेत्र है जो सभी दिए गए डेटा पॉइंट्स को कवर कर सकता है। ग्राहम स्कैन एल्गोरिदम कन्वेक्स हल के कॉर्नर पॉइंट्स ढूंढता है। इस एल्गोरिदम में, सबसे पहले सबसे निचले पॉइंट को चुना जाता है। वह पॉइंट कन्वेक्स हल का शुरुआती पॉइंट होता है। शेष n-1 वर्टेक्स को स्टार्ट पॉइंट से एंटी-