इस ट्यूटोरियल में, हम दी गई बिंदुओं के सेट का कन्वेक्स हल ढूंढने के लिए एक प्रोग्राम पर चर्चा करेंगे।
कन्वेक्स हल सबसे छोटा बहुभुज उत्तल आकृति है जो सभी दिए गए बिंदुओं को या तो सीमा पर या आकृति के अंदर समाहित करता है।
उदाहरण
#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)