Convex Hull (Bao lồi) thuật toán Monotone Chain trong C++

Tìm bao lồi của tập điểm dùng thuật toán Monotone Chain (Andrew's algorithm).

Bao lồi là đa giác lồi nhỏ nhất chứa tất cả điểm.

Chương trình 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;
}

Kết quả

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