हम C++ में टू डायमेंशन में गिफ्ट रैपिंग एल्गोरिदम को लागू करने के लिए एक प्रोग्राम विकसित करेंगे। गिफ्ट रैपिंग एल्गोरिदम दिए गए पॉइंट्स के सेट के कन्वेक्स हल की गणना करने के लिए एक एल्गोरिदम है।
एल्गोरिदम
Begin function convexHull() n पॉइंट्स के सेट का कन्वेक्स हल खोजने के लिए: कम से कम तीन पॉइंट्स होने चाहिए। परिणाम को इनिशियलाइज़ करें। सबसे बाएं पॉइंट को खोजें। सबसे बाएं पॉइंट से शुरू करके, काउंटरक्लॉकवाइज़ चलते रहें जब तक कि स्टार्ट पॉइंट पर फिर से न पहुंच जाएं। परिणाम प्रिंट करें। End
उदाहरण कोड
#include <iostream> using namespace std; #define INF 10000 struct P { int x; int y; }; int orient(P a, P b, P c) { int v = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y); if (v == 0) return 0; // colinear return (v >0) ? 1 : 2; // clock or counterclock wise } void convexHull(P points[], int m) { if (m < 3)//कम से कम तीन पॉइंट्स आवश्यक return; int n[m]; for (int i = 0; i < m; i++) n[i] = -1; int l = 0;//परिणाम इनिशियलाइज़ करें। for (int i = 1; i < m; i++) if (points[i].x < points[l].x) l = i; //सबसे बाएं पॉइंट को खोजें int p = l, q; do { q = (p + 1) % m; for (int i = 0; i < m; i++) if (orient(points[p], points[i], points[q]) == 2) q = i; n[p] = q; p = q; } while (p != l); for (int i = 0; i < m; i++) { if (n[i] != -1) cout << "(" << points[i].x << ", " << points[i].y << ")\n"; } } int main() { P points[] = {{0, 4}, {2, 1}, {2, 3}, {4, 1}, {3, 0}, {1, 1}, {7, 6}}; cout << "The points in the convex hull are: "; int n = sizeof(points) / sizeof(points[0]); convexHull(points, n); return 0; }आउटपुट
The points in the convex hull are: (0, 4) (4, 1) (3, 0) (1, 1) (7, 6)
