Convex Hull

Quick Revisit

• USE WHEN: need the convex hull of a point set -- prerequisite for diameter, min enclosing, farthest pair
• INVARIANT: stack maintains CCW turns; any CW turn triggers a pop
• TIME: O(n log n) | SPACE: O(n)
• CLASSIC BUG: using < 0 instead of <= 0 in cross product check, keeping collinear points on hull
• PRACTICE: ../12-practice-ladders/08-ladder-mixed.md

Andrew's monotone chain -- the standard $O(n\log n)$ algorithm for computing convex hulls in contests.

Difficulty: [Intermediate]Prerequisites: Geometry BasicsCF Rating Range: 1600 -- 2000

---

Contents

• 1. Intuition & Concept
• 2. Visual Intuition -- Full Walkthrough
• 3. C++ STL Reference
• 4. Implementation -- Contest-Ready
• 5. Operations Reference
• 6. Problem Patterns & Tricks
• 7. Contest Cheat Sheet
• 8. Gotchas & Debugging
• 9. Self-Test
• 10. Practice Problems
• 11. Further Reading

---

Intuition & Concept

Layer 1 -- The Problem

You have $n$ points scattered in the plane. Find the smallest convex polygon that contains every point.

Why do you care? Because a surprising number of harder problems reduce to "build the convex hull first":

• Farthest pair -- the two points at maximum distance must both lie on the hull.
• Smallest enclosing rectangle -- its sides must be flush with hull edges.
• Maximum area triangle -- its vertices are on the hull.
• Determining if a point set can be separated by a line -- check hull intersection.

The convex hull strips away the interior clutter and leaves you with the $h$ extreme points that define the outer boundary. Typically $h\ll n$, which makes subsequent queries much cheaper.

Layer 2 -- What "Convex" Means

A polygon is convex if, walking along its boundary, you never turn clockwise (or equivalently, every interior angle is less than 180 degrees).

The classic analogy: imagine hammering nails at each point on a board, then stretching a rubber band around all of them. The rubber band snaps to the convex hull.

  Rubber band analogy:

       . * .              The * points are on the hull.
     *       *            The . points are interior --
    *  .   .   *          the rubber band skips over them.
     *       *
       * . *

Formally: the convex hull of a point set $S$ is the smallest convex polygon $P$ such that every point of $S$ is inside or on the boundary of $P$.

Layer 3 -- The Core Weapon: Cross Product

Given three points $A$, $B$, $C$, the cross product of vectors $\overrightarrow{AB}$ and $\overrightarrow{AC}$ tells you the turn direction:

$$\text{cross}(A,B,C)=(B.x-A.x)(C.y-A.y)-(B.y-A.y)(C.x-A.x)$$

• Positive $\Rightarrow$ counter-clockwise (left turn)
• Zero $\Rightarrow$ collinear
• Negative $\Rightarrow$ clockwise (right turn)

   Left turn (cross > 0):        Right turn (cross < 0):

        C                              B
       /                                \
      /                                  \
     A------>B                  A-------->C

This is the entire geometric primitive you need. Andrew's algorithm is just a clever way of using this test repeatedly.

Layer 4 -- Andrew's Monotone Chain

The idea is beautifully simple:

1. Sort all points by $(x,y)$ -- leftmost first, break ties by $y$.
2. Build the lower hull: sweep left to right. Maintain a stack of points forming a chain that always turns counter-clockwise. When a new point causes a clockwise turn (or is collinear), pop the previous point -- it is interior, not on the hull boundary.
3. Build the upper hull: sweep right to left with the exact same logic.
4. Concatenate lower and upper hulls.

Why does sorting work? After sorting, the leftmost and rightmost points are guaranteed to be on the hull. The lower hull connects them along the bottom; the upper hull connects them along the top.

  The two sweeps:

  LOWER HULL (left to right):
  ============================
      Start                         End
        o------->---------->-------->o
       (leftmost)                 (rightmost)
       Keeps points that curve DOWN

  UPPER HULL (right to left):
  ============================
        o<--------<----------<------o
       (leftmost)                 (rightmost)
       Keeps points that curve UP

Layer 5 -- The Pop Rule Dissected

When building either hull, you maintain a stack. For each new point $P$:

  While the stack has >= 2 points:
    Let A = second-to-top, B = top
    If cross(A, B, P) <= 0:   // right turn or collinear
      Pop B                    // B is not on the hull
    Else:
      Break                    // left turn -- keep B
  Push P

The <= 0 condition excludes collinear points from the hull. If you need collinear boundary points (e.g., to count lattice points on the perimeter), change to < 0.

Why popping is safe: if $A$, $B$, $P$ make a right turn, then $B$ is "inside" the triangle formed by the preceding hull points and $P$. It can never be an extremal point, so removing it is correct.

Amortized $O(n)$: each point is pushed at most once and popped at most once. The total work across all push/pop operations is $O(n)$. Combined with the $O(n\log n)$ sort, the overall complexity is $O(n\log n)$.

  Convex Hull Stack Operations (Lower Hull Example):

  Step 1: Push A        Step 2: Push B        Step 3: P arrives
  +---+                 +---+                 cross(A,B,P) <= 0
  | A |                 | B |  <-- top        Pop B!
  +---+                 +---+                 +---+
                        | A |                 | A |
                        +---+                 +---+

  Step 4: Push P        Step 5: Push Q        Step 6: R arrives
  +---+                 +---+                 cross(P,Q,R) > 0
  | P |  <-- top        | Q |  <-- top        Keep Q, push R.
  +---+                 +---+                 +---+
  | A |                 | P |                 | R |  <-- top
  +---+                 +---+                 +---+
                        | A |                 | Q |
                        +---+                 +---+
                                              | P |
                                              +---+
                                              | A |
                                              +---+

What the Code Won't Teach You

When to reach for convex hull reduction. The hardest skill is recognizing that your problem reduces to a hull problem in the first place. "Given $n$ points, find the pair at maximum distance" -- most people think $O(n^2)$ brute force or some data structure. The insight is: the maximum-distance pair must be two hull vertices (farthest pair theorem). You need to know this before you read the statement of rotating calipers, not because you saw it in this notebook.

Practical experience with the pop invariant. Until you've stepped through 5-10 examples of the pop rule by hand -- including cases where multiple points get popped in a row -- the algorithm feels fragile. It isn't. The amortized $O(n)$ argument is exactly right. But you won't trust it until you've seen the invariant hold through complex multi-pop sequences.

The connection to the DP convex hull trick. The CHT maintains lines on a "hull" in dual space. If you understand geometric convex hulls, you understand why the CHT works. If you learned CHT as a magic optimization trick without understanding the geometric interpretation, you'll misapply it on problems with non-monotone queries.

---

Visual Intuition -- Full Walkthrough

Consider these 8 points:

  A(0,0)  B(2,1)  C(4,0)  D(5,3)  E(3,5)  F(1,4)  G(2,3)  H(3,2)

After sorting by $(x,y)$:

  A(0,0)  B(2,1)  F(1,4)  G(2,3)  H(3,2)  E(3,5)  C(4,0)  D(5,3)

Wait -- let me sort properly:

  (0,0) (1,4) (2,1) (2,3) (3,2) (3,5) (4,0) (5,3)
    A     F     B     G     H     E     C     D

Plot:

  y
  5 |              E
  4 |  F
  3 |        G        D
  2 |           H
  1 |     B
  0 | A           C
    +--+--+--+--+--+---> x
    0  1  2  3  4  5

Lower Hull Construction

Sweep left to right. Pop while cross $\le 0$ (discard right turns / collinear).

  Push A(0,0)                                Stack: [A]
  Push F(1,4)                                Stack: [A, F]
  B(2,1): cross(A, F, B) = (1)(1) - (4)(2) = 1 - 8 = -7 <= 0
          Pop F.                             Stack: [A]
          |stack| < 2, push B.               Stack: [A, B]
  G(2,3): cross(A, B, G) = (2)(3) - (1)(2) = 6 - 2 = 4 > 0
          Keep. Push G.                      Stack: [A, B, G]
  H(3,2): cross(B, G, H) = (0)(1) - (2)(1) = 0 - 2 = -2 <= 0
          Pop G.                             Stack: [A, B]
          cross(A, B, H) = (2)(2) - (1)(3) = 4 - 3 = 1 > 0
          Keep. Push H.                      Stack: [A, B, H]
  E(3,5): cross(B, H, E) = (1)(4) - (1)(1) = 4 - 1 = 3 > 0
          Keep. Push E.                      Stack: [A, B, H, E]
  C(4,0): cross(H, E, C) = (0)(-2) - (3)(1) = 0 - 3 = -3 <= 0
          Pop E.                             Stack: [A, B, H]
          cross(B, H, C) = (1)(-1) - (1)(2) = -1 - 2 = -3 <= 0
          Pop H.                             Stack: [A, B]
          cross(A, B, C) = (2)(0) - (1)(4) = 0 - 4 = -4 <= 0
          Pop B.                             Stack: [A]
          |stack| < 2, push C.               Stack: [A, C]
  D(5,3): cross(A, C, D) = (4)(3) - (0)(5) = 12 > 0
          Keep. Push D.                      Stack: [A, C, D]

  Lower hull: A -> C -> D

  y
  5 |
  4 |
  3 |                    D
  2 |                  /
  1 |              /
  0 | A--------C
    +--+--+--+--+--+---> x

Upper Hull Construction

Sweep the sorted list in reverse (right to left). Same pop rule.

  Reverse order: D(5,3) C(4,0) E(3,5) H(3,2) G(2,3) B(2,1) F(1,4) A(0,0)

  Push D(5,3)                                Stack: [D]
  Push C(4,0)                                Stack: [D, C]
  E(3,5): cross(D, C, E) = (-1)(2) - (-3)(-2) = -2 - 6 = -8 <= 0
          Pop C.                             Stack: [D]
          Push E.                            Stack: [D, E]
  H(3,2): cross(D, E, H) = (-2)(-1) - (2)(-2) = 2 + 4 = 6 > 0
          Keep. Push H.                      Stack: [D, E, H]
  G(2,3): cross(E, H, G) = (0)(1) - (-3)(-1) = 0 - 3 = -3 <= 0
          Pop H.                             Stack: [D, E]
          cross(D, E, G) = (-2)(0) - (2)(-3) = 0 + 6 = 6 > 0
          Keep. Push G.                      Stack: [D, E, G]
  B(2,1): cross(E, G, B) = (-1)(-2) - (0)(-1) = 2 - 0 = 2 > 0
          Keep. Push B.                      Stack: [D, E, G, B]
  F(1,4): cross(G, B, F) = (0)(3) - (-2)(-1) = 0 - 2 = -2 <= 0
          Pop B.                             Stack: [D, E, G]
          cross(E, G, F) = (-1)(1) - (0)(-2) = -1 <= 0
          Pop G.                             Stack: [D, E]
          cross(D, E, F) = (-2)(1) - (2)(-4) = -2 + 8 = 6 > 0
          Keep. Push F.                      Stack: [D, E, F]
  A(0,0): cross(E, F, A) = (-2)(-4) - (-1)(-3) = 8 - 3 = 5 > 0
          Keep. Push A.                      Stack: [D, E, F, A]

  Upper hull: D -> E -> F -> A

Merge

Lower hull: $A\to C\to D$. Upper hull: $D\to E\to F\to A$.

Remove the duplicate endpoints and combine:

  Hull (CCW): A(0,0) -> C(4,0) -> D(5,3) -> E(3,5) -> F(1,4)

  y
  5 |              E
  4 |  F--------/
  3 |   \           D
  2 |    \        /
  1 |     \    /
  0 | A----C
    +--+--+--+--+--+---> x

  Interior points: B(2,1), G(2,3), H(3,2) -- all correctly excluded.

Graham Scan -- The Alternative

Graham scan is the other classic $O(n\log n)$ hull algorithm:

1. Pick the bottom-most point (break ties by leftmost) as the pivot.
2. Sort remaining points by polar angle from the pivot.
3. Process points in angle order, maintaining a stack with the same turn check.

Why Andrew's is preferred in contests:

Aspect	Andrew's Monotone Chain	Graham Scan
Sort criterion	$(x,y)$ -- trivial	Polar angle -- trickier
Angle computation	Not needed	atan2 or cross-product comparisons
Collinear handling	Simpler	Fiddly at same angle
Code length	~15 lines	~20 lines
Correctness traps	Few	Angle sort ties

Both are $O(n\log n)$. Andrew's wins on simplicity.

Graham Scan -- Step-by-Step Trace

Same 8 points: $A(0,0),B(2,1),C(4,0),D(5,3),E(3,5),F(1,4),G(2,3),H(3,2)$.

Step 1: Pick the pivot -- lowest y (break ties by leftmost x) --> $A(0,0)$.

Step 2: Sort remaining points by polar angle from $A$:

  y
  5 |              E         Angles from A(0,0):
  4 |  F                       C: atan2(0,4) =  0 deg
  3 |        G        D        B: atan2(1,2) ~= 27 deg
  2 |           H               H: atan2(2,3) ~= 34 deg
  1 |     B                     D: atan2(3,5) ~= 31 deg
  0 | A           C             G: atan2(3,2) ~= 56 deg
    +--+--+--+--+--+---> x      E: atan2(5,3) ~= 59 deg
                                F: atan2(4,1) ~= 76 deg
  Sorted by angle: A, C, B, D, H, G, E, F

Step 3: Process points with a stack (push, pop on right turns):

  Process C(4,0):  Stack: [A, C]
                   (only 2 points, just push)

  Process B(2,1):  cross(A,C,B) = (4)(1)-(0)(2) = 4 > 0 -> LEFT turn OK
                   Stack: [A, C, B]         keep B

  Process D(5,3):  cross(C,B,D) = (-2)(3)-(1)(1) = -7 < 0 -> RIGHT turn X
                   Pop B.                   Stack: [A, C]
                   cross(A,C,D) = (4)(3)-(0)(1) = 12 > 0 -> LEFT OK
                   Stack: [A, C, D]         keep D

  Process H(3,2):  cross(C,D,H) = (1)(2)-(3)(-1) = 5 > 0 -> LEFT OK
                   Stack: [A, C, D, H]      keep H

  Process G(2,3):  cross(D,H,G) = (-2)(0)-(-1)(-3) = -3 < 0 -> RIGHT X
                   Pop H.                   Stack: [A, C, D]
                   cross(C,D,G) = (1)(0)-(3)(-2) = 6 > 0 -> LEFT OK
                   Stack: [A, C, D, G]      keep G

  Process E(3,5):  cross(D,G,E) = (-3)(2)-(0)(-2) = -6 < 0 -> RIGHT X
                   Pop G.                   Stack: [A, C, D]
                   cross(C,D,E) = (1)(2)-(3)(-1) = 5 > 0 -> LEFT OK
                   Stack: [A, C, D, E]      keep E

  Process F(1,4):  cross(D,E,F) = (-2)(1)-(2)(-4) = 6 > 0 -> LEFT OK
                   Stack: [A, C, D, E, F]   keep F

  Final hull (CCW): A(0,0) -> C(4,0) -> D(5,3) -> E(3,5) -> F(1,4)

  y
  5 |              E
  4 |  F--------/  |
  3 |   \          D
  2 |    \        /     Rejected: B, G, H (interior points)
  1 |     \    /        All rejected by RIGHT-turn detection.
  0 | A----C
    +--+--+--+--+--+---> x

---

Pop-Rule Policy: Collinear Points and Duplicates

The single line that decides everything is the comparison inside the pop loop:

while (h.size() >= 2 && cross(h.end()[-2], h.end()[-1], p) ??? 0) h.pop_back();

Replacing ??? selects one of three policies. Pick consciously — different problems want different conventions.

Policy	Pop condition	Collinear boundary points	Hull vertex count	When to use
Strict hull (default in this file)	<= 0	dropped — only "corner" vertices remain	$h$ minimal	Most contest problems: diameter, area, enclosing rectangle
Inclusive hull	< 0	kept — all boundary points listed	larger $h$	Counting lattice / boundary points, problems that ask for "all hull points"
Bug	< 0 with duplicate input points	duplicates re-emitted	corrupted	— — never run hull without unique(...) first

Duplicate inputs. The unique(...) call after sort(...) collapses identical points; without it, two coincident points fail the strict left-turn test in degenerate ways. Always deduplicate.

Returned ordering convention. The implementation below returns vertices in counter-clockwise order, with the first vertex not repeated at the end (the trailing duplicate added during construction is removed by h.pop_back() before return). Downstream algorithms in this chapter — rotating calipers, point-in-convex-polygon binary search, minimum enclosing rectangle — all assume this layout. If you switch to the inclusive policy (< 0), the final dedup may emit the leftmost or rightmost vertex twice; an extra equality check at the join is the fix.

---

C++ STL Reference

Function / Type	Header	What it does	Complexity
sort()	<algorithm>	Sort points lexicographically	$O(n\log n)$
unique()	<algorithm>	Remove consecutive duplicates	$O(n)$
tie(a, b)	<tuple>	Lexicographic comparison helper	$O(1)$
vector<P>	<vector>	Dynamic array for hull storage	Amortized $O(1)$ push
__int128	GCC built-in	128-bit int for huge coords	$O(1)$

---

Implementation -- Contest-Ready

Point struct (shared with all geometry code)

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

struct P {
    ll x, y;
    P operator-(P o) const { return {x - o.x, y - o.y}; }
    bool operator<(P o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(P o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
ll cross(P o, P a, P b) { return cross(a - o, b - o); }

Minimal contest template

vector<P> hull(vector<P> pts) {
    int n = pts.size();
    if (n < 2) return pts;
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    n = pts.size();
    if (n < 2) return pts;
    vector<P> h;
    for (auto& p : pts) {                              // lower hull
        while (h.size() >= 2 && cross(h.end()[-2], h.end()[-1], p) <= 0)
            h.pop_back();
        h.push_back(p);
    }
    int lo = h.size();
    for (int i = n - 2; i >= 0; i--) {                 // upper hull
        while ((int)h.size() > lo && cross(h.end()[-2], h.end()[-1], pts[i]) <= 0)
            h.pop_back();
        h.push_back(pts[i]);
    }
    h.pop_back();
    return h;
}

Explained version

// Returns convex hull vertices in counter-clockwise order.
// Collinear boundary points are EXCLUDED (change <= to < to include them).
vector<P> hull(vector<P> pts) {
    int n = pts.size();
    if (n < 2) return pts;

    // Step 1: sort by (x, then y). This guarantees the first and last
    // points in the sorted order are hull vertices (leftmost/rightmost).
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    n = pts.size();
    if (n < 2) return pts;

    vector<P> h;

    // Step 2: Lower hull -- sweep left to right.
    // Invariant: the points on the stack form a chain where consecutive
    // triples always turn left (counter-clockwise). If adding a new point
    // P makes the last triple turn right (cross <= 0), the middle point
    // is interior -- pop it.
    for (auto& p : pts) {
        while (h.size() >= 2 && cross(h.end()[-2], h.end()[-1], p) <= 0)
            h.pop_back();
        h.push_back(p);
    }

    // Step 3: Upper hull -- sweep right to left.
    // 'lo' marks the boundary: don't pop into the lower hull.
    int lo = h.size();
    for (int i = n - 2; i >= 0; i--) {
        while ((int)h.size() > lo && cross(h.end()[-2], h.end()[-1], pts[i]) <= 0)
            h.pop_back();
        h.push_back(pts[i]);
    }

    // The first point appears at the start and was also appended
    // at the end of the upper hull. Remove the duplicate.
    h.pop_back();
    return h;
}

Full solution for CSES 2195 -- Convex Hull

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

struct P {
    ll x, y;
    P operator-(P o) const { return {x - o.x, y - o.y}; }
    bool operator<(P o) const { return tie(x, y) < tie(o.x, o.y); }
    bool operator==(P o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
ll cross(P o, P a, P b) { return cross(a - o, b - o); }

vector<P> hull(vector<P> pts) {
    int n = pts.size();
    if (n < 2) return pts;
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    n = pts.size();
    if (n < 2) return pts;
    vector<P> h;
    for (auto& p : pts) {
        while (h.size() >= 2 && cross(h.end()[-2], h.end()[-1], p) <= 0)
            h.pop_back();
        h.push_back(p);
    }
    int lo = h.size();
    for (int i = n - 2; i >= 0; i--) {
        while ((int)h.size() > lo && cross(h.end()[-2], h.end()[-1], pts[i]) <= 0)
            h.pop_back();
        h.push_back(pts[i]);
    }
    h.pop_back();
    return h;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> pts(n);
    for (auto& [x, y] : pts) cin >> x >> y;
    auto h = hull(pts);
    cout << h.size() << "\n";
    for (auto& [x, y] : h) cout << x << " " << y << "\n";
}

---

Operations Reference

Operation	Time	Space	Notes
Sort points	$O(n\log n)$	$O(n)$	Dominates overall complexity
Build lower hull	$O(n)$	$O(n)$	Amortized -- each point pushed/popped once
Build upper hull	$O(n)$	$O(n)$	Same amortized argument
Overall convex hull	$O(n\log n)$	$O(n)$	Sort + two linear sweeps
Perimeter of hull	$O(h)$	$O(1)$	Sum of edge lengths
Area of hull	$O(h)$	$O(1)$	Shoelace formula
Point in convex hull	$O(\log h)$	$O(1)$	Binary search on sectors

---

Problem Patterns & Tricks

Pattern 1: "Build Hull, Then Query"

Most hull problems follow this two-phase structure: construct the hull in $O(n\log n)$, then answer queries on the hull in $O(h)$ or $O(\log h)$.

  Hull Problem Pipeline:

  Input       Phase 1           Phase 2          Output
  +-----+    +----------+    +-------------+    +--------+
  | n   |--->| Build    |--->| Query on    |--->| Answer |
  | pts |    | Hull     |    | h vertices  |    |        |
  +-----+    | O(nlogn) |    | O(h)/O(logh)|    +--------+
             +----------+    +-------------+

  h << n in most inputs -- this is the whole point.

auto h = hull(pts);
// Now work with h.size() points instead of n

CF Examples: CSES 2195, CF 166B

Pattern 2: "Farthest Pair via Rotating Calipers"

The two farthest points must be on the hull. Build hull, then use rotating calipers (see Rotating Calipers) to find the diameter in $O(h)$.

CF Examples: CF 1290A

Pattern 3: "Collinear Points on Hull Boundary"

Sometimes you need all points on the hull boundary, including collinear ones (e.g., for counting lattice points). Change <= 0 to < 0 in the pop condition.

// Include collinear boundary points:
while (h.size() >= 2 && cross(h.end()[-2], h.end()[-1], p) < 0)
    h.pop_back();

Warning: with collinear points included, the hull may have many more vertices. Some problems exploit this.

Pattern 4: "Convex Hull to Reduce Brute Force"

If a problem asks for some extremal quantity over all pairs/triples, and only hull points can contribute, build the hull and brute-force on $h$ points instead of $n$.

Example: maximum area triangle inscribed in $n$ points. The triangle vertices must be on the hull -- iterate over $O(h^2)$ pairs with a rotating pointer for the third vertex.

CF Examples: CF 1374E2

Pattern 5: "Online / Dynamic Hull"

Points arrive one at a time. Maintain the hull in a set<P> sorted by angle or $x$-coordinate. For each insertion, find the tangent lines and remove dominated points.

CF Examples: CF 70D

Pattern 6: "Upper/Lower Hull for Convex Hull Trick (DP)"

The DP convex hull trick (for optimizing $dp[i]=\underset{j}{min}(dp[j]+b_j\cdot a_i)$) maintains lines on a hull. Understanding the geometric hull makes the DP trick much more intuitive.

See: DP Convex Hull Trick

---

Contest Cheat Sheet

+================================================================+
|                     CONVEX HULL CHEAT SHEET                    |
+================================================================+
| ALGORITHM: Andrew's Monotone Chain                             |
|   1. Sort by (x, y)                                           |
|   2. Lower hull: L->R, pop while cross([-2],[-1],P) <= 0      |
|   3. Upper hull: R->L, pop while cross([-2],[-1],P) <= 0      |
|   4. Remove duplicate endpoint, return                         |
+----------------------------------------------------------------+
| CROSS PRODUCT:                                                 |
|   cross(A,B,C) = (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x)  |
|   > 0: left turn (CCW)    == 0: collinear    < 0: right turn  |
+----------------------------------------------------------------+
| COMPLEXITY: O(n log n) time, O(n) space                        |
+----------------------------------------------------------------+
| COLLINEAR POINTS:                                              |
|   <= 0 to exclude from hull    < 0 to include on edges        |
+----------------------------------------------------------------+
| KEY TEMPLATE:                                                  |
|   for (auto& p : pts) {                                       |
|       while (sz>=2 && cross(h[sz-2],h[sz-1],p)<=0) pop;       |
|       push(p);                                                 |
|   }                                                            |
+================================================================+

---

Gotchas & Debugging

Gotcha 1: Integer overflow

Coordinates up to ${10}^9$: cross product involves products of differences that can reach $2\times {10}^{18}$. This fits in long long ($\approx 9.2\times {10}^{18}$). But if you multiply two cross products (e.g., comparing angles), you overflow. Use __int128 for that.

Gotcha 2: Duplicate points

If the input has duplicate points, they can break the hull (two identical points have cross product 0 with anything). Always deduplicate after sorting:

pts.erase(unique(pts.begin(), pts.end()), pts.end());

Gotcha 3: All points collinear

If all points lie on a line, the hull degenerates to a segment (2 points with <= 0, or all points with < 0). Make sure downstream code handles hull.size() < 3.

Gotcha 4: n = 0 or n = 1

Edge cases that crash naively. Return early:

if (n < 2) return pts;

Gotcha 5: Confusing the pop condition direction

For lower hull: pop while cross $\le 0$ (not $\ge 0$). The condition is the same for both hulls in Andrew's algorithm -- the sweep direction (left-to-right vs right-to-left) handles the "upper vs lower" distinction. Do not flip the sign for the upper hull.

Gotcha 6: Off-by-one in upper hull loop

The upper hull loop starts at index n - 2 (not n - 1), because point n - 1 is already the last point of the lower hull. Similarly, h.pop_back() at the end removes the duplicate of the first point.

Gotcha 7: Output order

Andrew's monotone chain returns the hull in counter-clockwise order starting from the leftmost-bottom point. Some problems expect clockwise order -- just reverse the result.

Mental Traps

Trap: "I understand the cross product so I understand the algorithm."

Knowing that cross(A, B, C) > 0 means a left turn is not the same as knowing why popping the previous point when cross <= 0 gives you the correct hull. The connection: if cross(A, B, C) <= 0, then B is inside or on the boundary of the triangle formed by A, C, and the "extreme" direction -- it can never be an extremal point of the hull. That's why popping is always safe. Without this reasoning, you're just memorizing a magic condition.

Trap: "The lower hull goes bottom, the upper hull goes top."

After Andrew's sort, "lower hull" means "the path along the bottom from leftmost to rightmost" and "upper hull" means "the path along the top from rightmost to leftmost." These are not the geometrically lowest and highest points in general. A beginner's confusion: seeing a point with a high y-coordinate end up on the "lower hull" and concluding the code must be wrong. It isn't.

Trap: Thinking <= 0 vs < 0 is a minor style difference.

It's a semantic choice that completely changes what the hull contains:

• <= 0: collinear boundary points are excluded (standard for most geometry problems).
• < 0: collinear boundary points are included (needed for lattice-point-on-hull problems).

Switching between these without thought is how you get WA on problems asking "how many points lie on the hull boundary."

  Collinear point handling:

  cross <= 0 (exclude collinear):     cross < 0 (include collinear):
     A *-----------* C                   A *-----*-----* C
       (B removed from hull)                   B kept on hull

Trap: Assuming a hull problem is just about finding the hull.

Most hull problems are two-phase: build the hull, then do something with it (rotating calipers, binary search for extreme points, point-in-polygon queries). If you focus all your energy on building the hull correctly and then improvise the second phase, that's where the WA comes from. Read the full problem before writing code.

Debug checklist

  [ ] Used long long for coordinates and cross products?
  [ ] Deduplicated after sorting?
  [ ] Handled n <= 2?
  [ ] Pop condition uses <= 0 (or < 0 for collinear)?
  [ ] Upper hull loop starts at n-2, stops at 0?
  [ ] Final pop_back to remove duplicate first point?
  [ ] Output order matches problem requirements (CCW vs CW)?

---

Self-Test

Before moving on, verify you can do all of these without referencing the material above:

• [ ] Write the full hull function from memory (both sweeps, lo variable, final pop_back(), deduplication) in under 10 minutes.
• [ ] Explain why both the lower and upper hull sweeps use cross <= 0 -- not >= 0 for the upper hull. Specifically, how does the sweep direction handle the upper/lower distinction?
• [ ] State the one-character change needed to include collinear boundary points on the hull, and explain why it works.
• [ ] Name at least three problem types that require building a convex hull as a preprocessing step (not as the final answer).
• [ ] Identify the overflow risk when coordinates are up to ${10}^9$, explain why long long suffices for single cross products, and explain why multiplying two cross products might overflow.
• [ ] Trace the algorithm by hand on a set of 6+ points, including at least one multi-pop sequence, and verify the hull is correct.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Convex Hull	CSES 2195	Easy	Direct application of Andrew's
2	Polygon Area	CSES 2191	Easy	Shoelace on hull output
3	Point in Polygon	CSES 2192	Easy	Build hull, then point query
4	Protecting Sheep	CF 70D	Medium	Online convex hull maintenance
5	Polygon	CF 166B	Medium	Hull containment check
6	Robert Hood	Kattis	Medium	Hull + farthest pair
7	Smallest Enclosing Circle	CF 1059E	Medium	Hull reduces point set
8	Wall	POJ 1113	Medium	Hull perimeter + circle arcs
9	Beauty Contest	POJ 2187	Hard	Hull + rotating calipers
10	Fence	USACO Plat	Hard	Hull with collinear handling

---

Further Reading

• cp-algorithms: Convex Hull -- Andrew's Monotone Chain
• cp-algorithms: Graham Scan
• USACO Guide: Convex Hull
• CF Blog: Geometry for CP (Al.Cash)
• Victor Lecomte, Handbook of Geometry for Competitive Programmers

Cross-references within this notebook:

• Geometry Basics -- point struct, cross product, orientation
• Rotating Calipers -- diameter and width queries on the hull
• Half-Plane Intersection -- dual problem: intersection of half-planes
• DP Convex Hull Trick -- hull structure in DP optimization

---

The Aha Moment

A convex hull is just a sorted-order stack discipline: sort points by x-coordinate, then sweep left-to-right maintaining the invariant that consecutive edges always turn the same way. If the new point makes a "wrong turn" (clockwise on the upper hull, counter-clockwise on the lower hull), pop the stack. Andrew's monotone chain is essentially two monotone stack passes -- one for the upper hull and one for the lower hull.

Pattern Fingerprint

Fingerprint: "find the minimal enclosing convex polygon" -> Andrew's monotone chain O(n log n)

Fingerprint: "maximize/minimize dot product with query direction" -> convex hull + binary search on hull edges

Fingerprint: "eliminate dominated points" -> convex hull (dominated = interior to hull)

Rating Progression

CF Rating	What to Master
1200	Implement Andrew's monotone chain from scratch. Understand why sorting by x (then by y) is necessary. Know that the hull has at most $n$ vertices.
1500	Handle collinear points on hull edges (include or exclude based on problem). Use the hull for farthest-point queries. Online hull insertion.
1800	$O(\log n)$ point-in-convex-polygon via binary search on hull edges. Minkowski sum of two convex polygons. Convex hull trick for DP.
2100	Dynamic convex hull (insertion + deletion). Hull of hulls (merging two convex hulls in $O(n)$). 3D convex hull concepts. Applying duality transforms.

Before You Code Checklist

• [ ] Did I sort points by x-coordinate first, breaking ties by y-coordinate?
• [ ] Does my cross-product check use <= (to exclude collinear points from the hull) or < (to include them), matching the problem's requirement?
• [ ] Am I building both the upper and lower hulls, and combining them correctly (avoiding duplicate endpoints)?
• [ ] Have I handled the edge case where all points are collinear (hull degenerates to a segment)?
• [ ] Is my cross() function using long long to avoid overflow?

What Would You Do If...?

Scenario 1: The problem asks for the convex hull but requires collinear points on the hull boundary to be included.

Answer: In Andrew's algorithm, change the pop condition from cross(...) <= 0 (which removes collinear points) to cross(...) < 0 (which keeps them). Be careful: this only keeps collinear points on hull edges, not interior collinear points. Also, the last edge of each half-hull needs special handling -- you may need to reverse-sort the final collinear segment.

Scenario 2: You need to answer thousands of "is point P inside the convex hull?" queries after building the hull.

Answer: Don't do O(n) per query. Pick the first hull vertex as an "anchor." The hull edges from this anchor divide the plane into angular sectors. Binary search on the angle to find which sector P falls in, then do one cross-product test. This gives $O(\log n)$ per query.

Scenario 3: Your convex hull code gives the wrong answer when the input has many duplicate points.

Answer: Duplicate points produce zero-length edges and zero cross products. The simplest fix: deduplicate the point set before running the hull algorithm. Alternatively, ensure your cross-product comparison uses < (strict) so that duplicate points are naturally discarded during the stack phase.

The Mistake That Teaches

I had a clean convex hull implementation that had passed dozens of problems. Then I hit a problem that said: "output hull vertices in counter-clockwise order, including all collinear boundary points."

My first instinct: just change cross(...) <= 0 to cross(...) < 0 in the pop condition. Submitted -- WA. The issue was subtle: the last edge of the upper hull (and lower hull) connected back to a shared endpoint. When collinear points existed on that final edge, they appeared in reverse order because the sweep had already passed them.

The fix: after building each half-hull with < 0, I had to sort the collinear points on the last edge of the lower hull in reverse order before concatenating. It took me two hours of drawing pictures on paper to finally see it. Lesson: "include collinear" is never a one-line change -- it ripples into endpoint handling.

Debug This

Bug 1: This convex hull sometimes includes interior points.

vector<Point> convexHull(vector<Point> pts) {
    sort(pts.begin(), pts.end());
    int n = pts.size(), k = 0;
    vector<Point> hull(2 * n);
    // Lower hull
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(hull[k-2], hull[k-1], pts[i]) < 0)
            k--;
        hull[k++] = pts[i];
    }
    // Upper hull
    int lower_size = k + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (k >= lower_size && cross(hull[k-2], hull[k-1], pts[i]) < 0)
            k--;
        hull[k++] = pts[i];
    }
    hull.resize(k - 1);
    return hull;
}

What's the bug?

The pop condition cross(...) < 0 only removes clockwise turns but keeps collinear points (cross product = 0). For a standard convex hull that excludes collinear boundary points, the condition should be cross(...) <= 0. Interior collinear points slip through and appear on the hull.

while (k >= 2 && cross(hull[k-2], hull[k-1], pts[i]) <= 0)

Bug 2: This hull is missing vertices -- it returns fewer points than expected.

vector<Point> convexHull(vector<Point> pts) {
    sort(pts.begin(), pts.end());
    int n = pts.size(), k = 0;
    vector<Point> hull(2 * n);
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(hull[k-2], hull[k-1], pts[i]) <= 0)
            k--;
        hull[k++] = pts[i];
    }
    int lower_size = k;
    for (int i = n - 2; i >= 0; i--) {
        while (k >= lower_size && cross(hull[k-2], hull[k-1], pts[i]) <= 0)
            k--;
        hull[k++] = pts[i];
    }
    hull.resize(k - 1);
    return hull;
}

What's the bug?

lower_size should be k + 1, not k. Using k means the upper-hull loop's while condition k >= lower_size can pop the last point of the lower hull. That last point is the rightmost point and must be shared between both halves. Changing to int lower_size = k + 1; protects it from being popped during the upper hull pass.

Bug 3: The hull output has a duplicate point at the end.

vector<Point> convexHull(vector<Point> pts) {
    sort(pts.begin(), pts.end());
    int n = pts.size(), k = 0;
    vector<Point> hull(2 * n);
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(hull[k-2], hull[k-1], pts[i]) <= 0)
            k--;
        hull[k++] = pts[i];
    }
    int lower_size = k + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (k >= lower_size && cross(hull[k-2], hull[k-1], pts[i]) <= 0)
            k--;
        hull[k++] = pts[i];
    }
    hull.resize(k);
    return hull;
}

What's the bug?

The final hull.resize(k) should be hull.resize(k - 1). The upper hull pass ends by re-adding the very first point (the leftmost point), which is already the starting point of the lower hull. Keeping it produces a duplicate. Using k - 1 removes this repeated vertex.

Historical Origin

The convex hull problem is often called the "Drosophila of computational geometry" -- a phrase coined by Preparata and Shamos in their 1985 textbook. Andrew's monotone chain algorithm (1979) simplified the earlier Graham scan (1972) by replacing the angular sort with a simple lexicographic sort, making it easier to implement and less prone to numerical issues.

Mnemonic Anchor

"Sort by X, sweep right for the floor, sweep left for the roof. Pop anything that turns right." — that is Andrew's monotone chain in one sentence.

Common Mistakes

• Collinear handling. Strict < 0 keeps collinear boundary points; <= 0 strips them. Pick the policy the problem wants — and remember the upper/lower-hull join needs a dedup pass under the inclusive policy.
• Broken comparator. a.x < b.x || a.y < b.y is not lexicographic ordering and produces UB inside std::sort. Use tie(a.x, a.y) < tie(b.x, b.y).
• Missing lower hull. Building only one sweep gives half the boundary.
• Integer overflow. Cross product of coordinates up to ${10}^9$ overflows 32-bit int; use long long.
• Skipping unique. Coincident input points produce zero-length edges and zero cross products; deduplicate before the sweep.

---

Recap and Cross-Links

Concept	Link
Geometry Basics	01-geometry-basics
Rotating Calipers	03-rotating-calipers
Half-Plane Intersection	04-half-plane-intersection
Practice	Ladder - Mixed