মনোটোন চেইন অ্যালগরিদম দিয়ে কনভেক্স হাল C++-এ

সমস্যা বিবরণ

পয়েন্ট সেট থেকে কনভেক্স হাল বের করতে হবে মনোটোন চেইন অ্যালগরিদম (Monotone Chain Algorithm) ব্যবহার করে।

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)