Convex Hull (monotone chain algorithm)

monotoneChain.cpp

// https://cses.fi/problemset/task/2195/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll crossProd(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}

vector<pair<ll, ll>> convexHull(vector<pair<ll, ll>> points) {
    sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());

    if (points.size() < 3) {
        return points;
    }

    vector<pair<ll, ll>> res = {points[0]};

    for (ll i = 1; i < points.size(); i++) {
        while (res.size() > 1 && crossProd(res[res.size() - 2], res.back(), points[i]) > 0) {
            res.pop_back();
        }

        res.push_back(points[i]);
    }

    ll lowerHullLen = res.size();

    for(ll i = points.size() - 2; i >= 0; i--) {
        while(res.size() > lowerHullLen && crossProd(res[res.size() - 2], res.back(), points[i]) > 0) {
            res.pop_back();
        }

        res.push_back(points[i]);
    }

    res.pop_back();

    return res;
}

int main() {
    ll n;
    cin >> n;

    vector<pair<ll, ll>> points(n);

    for (auto& i : points) {
        cin >> i.first >> i.second;
    }

    auto ans = convexHull(points);

    cout << ans.size() << '\n';

    for(auto [a, b] : ans) {
        cout << a << ' ' << b << '\n';
    }
}