Rotating Calipers — Contest Template

Companion to: 03-rotating-calipers.md. That file is the conceptual lesson (antipodal-pair theory, monotonicity proof, applications catalog). This file is the lean implementation reference: the diameter template plus the wrap-around / collinear / hull-size edge cases that bite under contest time.

Quick Revisit

• USE WHEN: diameter, width, or extremal-distance query on a convex hull
• INVARIANT: antipodal vertex advances monotonically as edge pointer walks the hull
• TIME: O(n) after O(n log n) hull construction | SPACE: O(n)
• CLASSIC BUG: not handling wrap-around — j must advance mod h, and you must complete a full cycle
• PRACTICE: 08-ladder-mixed

A two-pointer technique on convex hulls that answers diameter, width, and extremal-distance queries in linear time -- the secret weapon for turning $O(n^2)$ hull queries into $O(n)$.

Difficulty: [Advanced]Prerequisites: Convex HullCF Rating Range: 1700 -- 2200

---

The Core Idea

You have a convex hull with $h$ vertices. You want the diameter -- the maximum distance between any two vertices.

Brute force checks all $(\genfrac{}{}{0ex}{}{h}{2})$ pairs. Rotating calipers exploits a monotonicity property: as you walk edge-by-edge around the hull, the farthest vertex from each edge advances monotonically around the hull too.

Think of a physical caliper -- two parallel plates squeezing an object. Rotate the plates slowly around the hull. One plate touches an edge; the opposite plate touches the farthest vertex. As the edge advances, the farthest vertex only moves forward, never backward.

        B -------- C
       / \caliper/  \
      /   \ gap /    \       Rotate the "caliper" around the hull.
     /     \   /      \      For each edge (bottom plate), the
    A-------\-/--------D     farthest vertex (top plate) advances
             E                monotonically.

  Edge A->B: farthest = C     Two pointers: i walks edges,
  Edge B->C: farthest = E              j walks the antipodal vertex.
  Edge C->D: farthest = A     Total: O(h) iterations.

The Algorithm

i = 0 (edge pointer)
j = 1 (antipodal vertex pointer)
for each edge i -> i+1:
    while triangle(hull[i], hull[i+1], hull[j+1]) has greater height
          than triangle(hull[i], hull[i+1], hull[j]):
        j = j + 1 (mod h)
    update answer with dist(hull[i], hull[j])

The "height" comparison uses the cross product: cross(hull[i+1] - hull[i], hull[j] - hull[i]) gives twice the area of the triangle, which is proportional to the distance from hull[j] to edge $i$.

Implementation -- Diameter

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P { ll x, y; };

ll dist2(P a, P b) { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); }
ll cross(P o, P a, P b) {
    return (ll)(a.x-o.x)*(b.y-o.y) - (ll)(a.y-o.y)*(b.x-o.x);
}

// hull: convex hull vertices in CCW order
ll diameter_sq(vector<P>& hull) {
    int n = hull.size();
    if (n == 1) return 0;
    if (n == 2) return dist2(hull[0], hull[1]);

    ll best = 0;
    int j = 1;
    for (int i = 0; i < n; i++) {
        int ni = (i+1) % n;
        // advance j while the triangle area increases
        while (cross(hull[i], hull[ni], hull[(j+1)%n])
             > cross(hull[i], hull[ni], hull[j]))
            j = (j+1) % n;
        best = max(best, max(dist2(hull[i], hull[j]),
                             dist2(hull[ni], hull[j])));
    }
    return best;
}

Beyond Diameter

Application	Modification
Minimum width	For each edge, find the farthest vertex. Width = min distance from vertex to edge line.
Maximum distance between two convex hulls	Run calipers on both hulls simultaneously -- four pointers instead of two.
Minimum enclosing rectangle	One side of the optimal rectangle is flush with a hull edge. Rotate calipers to try all edges, track extreme projections.
Merge convex hulls	Find upper and lower tangents using caliper-style advancing.

Why Not Just $O(h^2)$?

For most contest problems, $h$ is small enough that $O(h^2)$ works. Rotating calipers matters when:

• $h$ can be $O(n)$ (points on a circle, no interior points)
• The problem chains hull construction with diameter queries and overall $O(n\log n)$ is required
• You need to solve the problem for many point sets (online queries)

In practice, having the $O(n)$ technique costs almost nothing extra in code length and eliminates the risk of TLE on worst-case inputs.

Gotchas

Trap	Fix
Hull has collinear points -> antipodal "vertex" is actually an edge	Check both endpoints of the antipodal edge
Hull size 1 or 2	Handle as special cases before the loop
Using >= instead of > in the advancing condition	Can cause infinite loop; use strict >
Forgetting mod n wraparound	The caliper must complete a full revolution

Self-Test

Q1. Why does the antipodal vertex only advance forward (never backward) as you iterate edges?

Answer

The function "distance from vertex $j$ to the line through edge $i$" is unimodal as $j$ walks around a convex hull. As edge $i$ rotates to $i+1$, the peak of this function only shifts forward, never backward — within a single edge step the inner `while` may advance $j$ multiple positions, but the *total* forward movement of $j$ across the whole loop is bounded by $h$. That total-monotonicity makes the two-pointer approach correct and $O(n)$ overall.

Q2. The diameter of a convex polygon is achieved by two vertices. Must these vertices be antipodal (i.e., one is the farthest from the edge adjacent to the other)?

Answer

Yes. The diameter pair must be an antipodal pair. If vertices $u$ and $v$ achieve the maximum distance, then $v$ must be farthest from at least one edge incident to $u$ (and vice versa). The rotating calipers enumerate all antipodal pairs, so the diameter is found.

Q3. What breaks if the hull has collinear points (three or more consecutive vertices on a line)?

Answer

The cross product between consecutive edges becomes zero, so the advancing condition `cross(...) > cross(...)` may not advance $j$ when it should. The fix: when cross products are equal, advance $j$ and also check both endpoints of the "flat" edge for the answer. Some implementations handle this by checking `dist(hull[i], hull[j])` AND `dist(hull[ni], hull[j])`.

Q4. Rotating calipers find the diameter in $O(n)$ given the hull. What is the total complexity including hull construction?

Answer

$O(n \log n)$ for sorting + $O(n)$ for hull construction + $O(h)$ for rotating calipers = $O(n \log n)$ total, where $h \le n$ is the hull size.

Practice Problems

Problem	What it tests
CSES -- Convex Hull + Diameter	Build hull, then calipers for diameter
CF 333E -- Summer Earnings	Farthest pair as subroutine
POJ 2187 -- Beauty Contest	Classic diameter of point set
CF 1195F -- Geometers Anonymous Club	Hull + caliper-based queries
UVa 10173 -- Smallest Bounding Rectangle	Rotating calipers for enclosing rectangle

---