C++ প্রোগ্রাম: টু-ডাইমেনশনাল গিফ্ট র্যাপিং অ্যালগরিদম ইমপ্লিমেন্টেশন

আমরা দুই মাত্রায় গিফ্ট র্যাপিং অ্যালগরিদম ইমপ্লিমেন্ট করার একটি C++ প্রোগ্রাম विकাশ করব। গিফ্ট র্যাপিং অ্যালগরিদম একটি দिये गये পয়েন্ট সেটের কনভেক্স হাল (convex hull) খুঁজে বের করার অ্যালগরিদম।

অ্যালগরিদম

শুরু
    convexHull() ফাংশন - n সংখ্যক পয়েন্টের কনভেক্স হাল বের করতে:
        কমপক্ষে তিনটি পয়েন্ট থাকতে হবে।
        রেজাল্ট ইনিশিয়ালাইজ করো।
        বামপাশের পয়েন্টটি খুঁজে বের করো।
        বামপাশের পয়েন্ট থেকে শুরু করে কাউন্টারক্লকওয়াইজ ঘুরতে থাকো
        যতক্ষণ না শুরুর পয়েন্টে ফিরে আসা হয়।
        রেজাল্ট প্রিন্ট করো।
শেষ

উদাহরণ কোড

#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; // কোলিনিয়ার 
    return (v > 0) ? 1 : 2; // ক্লকওয়াইজ বা কাউন্টারক্লকওয়াইজ 
} 
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)