Convex Hull (Andrew's)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Point {
    ll x, y;
    Point(ll x = 0, ll y = 0) : x(x), y(y) {}
    Point operator-(const Point &p) const { return {x - p.x, y - p.y}; }
    ll cross(const Point &p) const { return x * p.y - y * p.x; }
    ll dist(const Point &p) const { return (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y); }
    bool operator<(const Point &p) const { return x < p.x || (x == p.x && y < p.y); }
    friend istream &operator>>(istream &in, Point &p) { return in >> p.x >> p.y; }
};

vector<Point> convexHull(vector<Point> pts, bool includeCollinear = false) {
    int n = pts.size();
    if (n < 2) return pts;
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end(), [](const Point &a, const Point &b) {
        return a.x == b.x && a.y == b.y;
    }), pts.end());
    n = pts.size();
    if (n < 2) return pts;

    vector<Point> hull;
    auto check = [&](const Point &p) -> bool {
        ll cr = (hull.back() - hull[hull.size()-2]).cross(p - hull.back());
        return includeCollinear ? cr < 0 : cr <= 0;
    };

    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && check(pts[i])) hull.pop_back();
        hull.push_back(pts[i]);
    }
    int lower = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while ((int)hull.size() > lower && check(pts[i])) hull.pop_back();
        hull.push_back(pts[i]);
    }
    hull.pop_back();
    return hull;
}