vi. Dynamic Convex Hull

Maintains the convex hull of a growing point set: insert a point, test whether a point is inside or on the hull, in $O(\log n)$ amortized per operation.

DynamicHull h;
h.insert(P{x, y});
bool in = h.contains(p);           // inside or on the boundary of the current hull
vector<P> v = h.vertices();        // CCW, strict vertices, starting at the leftmost-lowest

Idea: keep the upper and lower hulls separately, each as a map<ll,ll> from $x$ to $y$ (the lower hull is stored as the upper hull of the points reflected through the $x$-axis, i.e. $(x,-y)$, so both chains use the same code). A new point outside a chain removes the neighbours on each side that stop being convex, exactly as in the stack-popping step of monotone chain, but anchored by a BST instead of an array so insertion doesn’t need a sorted-from-scratch pass. Coordinates up to $\sim 10^9$ keep the cross products in the proof below inside __int128 comfortably.

struct UpperHull {
    map<ll, ll> pts;                                       // x -> y, a strictly concave chain
 
    static i128 turn(ll ax, ll ay, ll bx, ll by, ll cx, ll cy) {  // cross(b - a, c - a)
        return (i128)(bx - ax) * (cy - ay) - (i128)(by - ay) * (cx - ax);
    }
    bool below(ll x, ll y) const {                          // (x, y) on or under the chain
        if (pts.empty()) return false;
        auto it = pts.lower_bound(x);
        if (it == pts.end()) return false;                  // right of the whole chain
        if (it->first == x) return y <= it->second;
        if (it == pts.begin()) return false;                // left of the whole chain
        auto pv = prev(it);
        return turn(pv->first, pv->second, it->first, it->second, x, y) <= 0;
    }
    void insert(ll x, ll y) {
        if (below(x, y)) return;                             // strictly under: no change needed
        pts[x] = y;
        auto it = pts.find(x);
        while (it != pts.begin()) {                          // remove left neighbours no longer on the chain
            auto a = prev(it);
            if (a == pts.begin()) break;
            auto b = prev(a);
            if (turn(b->first, b->second, a->first, a->second, x, y) >= 0) pts.erase(a);
            else break;
        }
        while (next(it) != pts.end()) {                      // remove right neighbours no longer on the chain
            auto a = next(it), b = next(a);
            if (b == pts.end()) break;
            if (turn(x, y, a->first, a->second, b->first, b->second) >= 0) pts.erase(a);
            else break;
        }
    }
};
 
struct DynamicHull {
    UpperHull upper, lower;                                  // lower stores (x, -y)
 
    void insert(P p) { upper.insert(p.x, p.y); lower.insert(p.x, -p.y); }
    bool contains(P p) const { return upper.below(p.x, p.y) && lower.below(p.x, -p.y); }
    vector<P> vertices() const {
        vector<P> res;
        for (auto& [x, y] : lower.pts) res.push_back({x, -y});
        for (auto it = upper.pts.rbegin(); it != upper.pts.rend(); ++it) {
            P p{it->first, it->second};
            if (!res.empty() && (p == res.back() || p == res.front())) continue;
            res.push_back(p);
        }
        return res;
    }
};

Complexity: $O(\log n)$ amortized per insert and query. Deletions: offline divide and conquer over time (if all operations are known in advance), or the $O({\log }^{2}n)$ Overmars-van Leeuwen structure (a BST of hull edges with each node storing enough to support true online deletion) — both are substantial, and avoidable in most contest problems (see the escape hatches).

Proof: UpperHull is correct, and the amortized bound

below. For $(x,y)$ with $x$ exactly matching a chain point, “on or under” the chain at that $x$ is literally $y\le$ the stored value. Otherwise $x$ falls strictly between consecutive chain points $pv,it$ (or outside the whole range, handled by the two early returns, correctly treated as “not below” so that an insert there always proceeds — an extreme point is never redundant): $\mathrm{turn}(pv,it,(x,y))=\mathrm{cross}(it-pv,(x,y)-pv)\le 0$ says $(x,y)$ is on the clockwise (non-left) side of the directed segment $pv\to it$, which — since the chain is concave from above (upper hull) and $pv.x<it.x$ — is exactly “on or below the segment”, the same orientation test used throughout Primitives.

insert. If below holds, $(x,y)$ is weakly inside the current upper region and changes nothing. Otherwise it lies strictly above the chain at its $x$, so it must become part of the new chain; inserting pts[x]=y tentatively adds it (overwriting any old point at the same $x$, which is necessarily now redundant since the new point is strictly higher by the below check having failed). The two while loops then remove left and right neighbours exactly as monotone chain’s stack-pop step does: a neighbour $a$ with left-neighbour $b$ is redundant once $\mathrm{turn}(b,a,(x,y))\ge 0$ — i.e. $a$ is on or above segment $b\to (x,y)$, meaning the chain can skip straight from $b$ to the new point without $a$, since including $a$ would no longer be concave (the one-sided analogue of the monotone-chain pop condition, proved there). Each while loop re-reads its neighbours after every erase, so it correctly cascades through multiple now-redundant points, not just one, stopping exactly when the chain is concave again on that side. Map iterators to elements other than the one erased stay valid, so it survives the whole process.

Lower hull via reflection. Reflecting every point through the $x$-axis ($y\mapsto -y$) turns “upper hull” into “lower hull” and vice versa (a reflection is an isometry that reverses which side is “up”), so running the identical UpperHull logic on $(x,-y)$ and negating back gives the true lower hull — this is why one piece of code serves both chains.

contains. A point is inside or on the convex region iff it is weakly below the upper chain and weakly above the lower chain, i.e. weakly below the reflected lower chain in reflected coordinates — exactly the two below calls.

Amortized $O(\log n)$. Each map operation (find, insert, erase, lower_bound) is $O(\log n)$. A point can be erased from the chain at most once over the whole run (once removed, it is gone forever — these structures never reinsert a previously-erased point), so the total work done by all the while-loop erasures across $n$ insertions is $O(n)$ map operations, $O(n\log n)$ total — amortized $O(\log n)$ per insertion, by the standard aggregate argument (charge each erasure to the point being erased, which pays for it exactly once). $■$

Tested: DynamicHull built by inserting $n$ random points one at a time; after every insertion, vertices() is checked against monotone chain recomputed from scratch on all points inserted so far (same vertex set), and contains is checked against the from-scratch hull’s inConvex/inPolygon test on a grid of query points.