⚙️AlgorithmIntermediate

Rotating Calipers

Key Points

•
Rotating calipers is a geometric two-pointer technique that sweeps two (or more) parallel support lines around a convex polygon.
•
As the calipers rotate, the opposite contact point moves monotonically, so each index advances at most once, yielding O(n) time on a convex n-gon.
•
It solves the convex polygon diameter (farthest pair), minimum width, minimum-area bounding rectangle, and enumerates all antipodal pairs.
•
The method must be run on a convex polygon, so compute a convex hull first in O(n $lo g$ n), then run calipers in O(n).
•
Distances and projections are computed using cross and dot products; using squared distances avoids unnecessary square roots.
•
For the minimum-area rectangle, maintain four calipers (left, right, top, bottom) aligned to the current edge’s direction and normal.
•
Numeric robustness matters: handle collinear edges, duplicate points, and floating-point tolerances carefully.
•
The key theoretical tool is the support function $h_{K}$ (u) and the fact that extrema along a fixed direction occur at vertices of the convex hull.

Prerequisites

→Convex hull algorithms (Andrew’s monotone chain) — Rotating calipers assumes a convex polygon in CCW order; building it correctly is essential.
→Dot and cross products in 2D — Projections and perpendicular distances are computed with dot and cross products.
→Two-pointer/monotone techniques — Understanding why indices advance monotonically clarifies the O(n) behavior.
→Floating-point precision and EPS handling — Comparisons in geometry often require tolerances to avoid instability.
→Modular indexing and cyclic arrays — Calipers walk around the polygon and wrap indices modulo the number of vertices.

Detailed Explanation

Tap terms for definitions

01Overview

Rotating calipers is a classic technique in computational geometry used on convex polygons. Imagine placing two parallel lines (calipers) on opposite sides of a convex shape so that they just touch it. Now rotate these lines together while keeping them parallel and always touching the polygon. As the lines rotate, the contact points on the polygon slide along edges and jump at vertices. The remarkable property is monotonicity: when we fix one caliper at a vertex/edge and rotate to the next event, the antipodal contact (on the opposite side) only moves forward around the polygon, never backward. This allows us to process all relevant pairs in linear time.

Many important geometric problems reduce to querying extremes of a convex polygon along a direction. Examples include: the polygon’s diameter (the farthest pair of points), the minimum width (closest pair of parallel supporting lines), and the minimum-area bounding rectangle. Rotating calipers offers simple, elegant, and efficient O(n) solutions once the convex hull is available. The technique relies on basic linear algebra—dot and cross products—to compare projections and distances to lines. The workflow is typically: compute the convex hull of the input points (O(n log n)), then apply one or several caliper sweeps (O(n)) to get the final answer.

02Intuition & Analogies

Picture a convex polygon as a rigid object on a table. Hold two long rulers so that they are parallel and gently squeeze the polygon from opposite sides; the rulers stop when they touch the boundary. Now, without losing contact, rotate both rulers together around the shape. As they rotate, different parts of the polygon take turns touching the rulers—sometimes an edge lies flush against a ruler, sometimes a vertex just kisses it. Because the polygon is convex, when one ruler moves forward along the boundary, the other ruler’s contact point must also move forward (or stay put); it never needs to backtrack—this is the essence of the monotone movement.

Why does this help? Many measurements depend on how far the shape extends in a direction. The distance between the two rulers is exactly the polygon’s “width” in the direction perpendicular to the rulers. If you keep track of the farthest two points that appear simultaneously on opposite rulers during the sweep, you can find the polygon’s diameter. If you run four rulers (left-right-top-bottom) and keep them fitted to the polygon while rotating, you can read the length and height at each angle and pick the smallest enclosing rectangle. These ideas mirror familiar two-pointer patterns from arrays: we walk indices in one pass because, thanks to convexity, the extrema change predictably as we rotate.

So the visual is: rulers touch, rotate, slide along edges, and only move forward. The calculations behind this picture boil down to projecting points onto directions (dot product) and measuring perpendicular distances to lines (cross product), which can be done quickly without heavy trigonometry.

03Formal Definition

Let K

\subset

R^{2}

be a convex polygon with vertices listed counterclockwise. For a unit direction vector u

\in

S^{1}

, the support function of K is

h_{K}

(u) =

max_{x \in K}

⟨

x, u

⟩

. Two support lines orthogonal to u are

L^{+}

(u):

⟨

x, u

⟩

h_{K}

(u) and

L^{-}

(u):

⟨

x, u

⟩

= -

h_{K}

(-u). The width of K in direction u is w(u) =

h_{K}

(u) +

h_{K}

(-u), the separation between these parallel support lines. A pair (p, q) of boundary points of K is antipodal if there exists a direction u such that p

\in

L^{+}

(u) and q

\in

L^{-}

(u). The rotating calipers method traces antipodal pairs as u rotates from 0 to 2

π

, advancing each contact point monotonically along the polygon’s boundary. The farthest pair (diameter) of K is realized by at least one antipodal pair of vertices. The minimum-width direction occurs when u is orthogonal to some edge of K, and the minimum-area bounding rectangle occurs at an orientation where one rectangle side is flush with an edge of K. Algorithmically, let the polygon be P = (

p_{0}

p_{1}

\dots

p_{m - 1}

) in CCW order. For each edge

e_{i} = p_{i + 1} - p_{i}

, we align a caliper with

e_{i}

and move the opposite contact index j to maximize the perpendicular distance

∣ e_{i} \times (p_{j} - p_{i}) ∣

∣ e_{i} ∥

. Because the function is unimodal over the cycle, j increases monotonically with i. Similar monotone updates hold for extremal projections onto the edge direction and its perpendicular, enabling O(m) scans.

04When to Use

Use rotating calipers whenever the task is to extract extremal measurements of a convex polygon along directions—as soon as you have its convex hull. Prime examples include: computing the diameter (farthest pair of points), finding the minimum width (the closest distance between two parallel supporting lines), and determining the minimum-area (or minimum-perimeter) enclosing rectangle. In all these problems, evaluating a quantity at a specific angle depends only on directional projections or perpendicular distances, which change smoothly and allow monotone pointer updates.

It is also useful when comparing two convex polygons: the distance between them, Minkowski sums, or collision-time queries can leverage support directions and rotating extrema. In competitive programming, a common pipeline is: read points, compute the convex hull (e.g., Andrew’s monotone chain), then run rotating calipers in O(n) to produce the final metric. This pattern is ideal for inputs up to 10^5 points because the convex hull dominates the cost (O(n \log n)) and the calipers sweep is linear.

Avoid using rotating calipers on non-convex inputs directly; always convexify first. If you only need a single farthest pair from an arbitrary set, either compute the hull first or use other methods; the calipers guarantee correctness and speed specifically on convex polygons.

⚠️Common Mistakes

• Skipping the convex hull: Running calipers on the raw (possibly non-convex) point set breaks the monotonicity guarantee and yields wrong answers. Always compute the convex hull first and ensure its vertices are in strict CCW order. • Mishandling collinearity: If the hull keeps all collinear boundary points, the sweep can duplicate states or cycle incorrectly. A standard fix is to remove intermediate collinear points on hull edges (use \le in the hull turn test) or handle ties carefully during pointer advancement. • Floating-point pitfalls: Comparing cross/dot values with exact inequalities can be unstable. Use an EPS tolerance and prefer squared distances to avoid unnecessary square roots. If input is integral and large, watch for overflow; use 64-bit or long double as appropriate. • Wrong pointer updates: In diameter and width sweeps, the comparison should be strictly on the signed area or projection increase in the current direction. Forgetting to wrap indices modulo m or failing to allow equal increases (ties) can miss valid antipodal pairs. • Orientation and units: Confusing edge direction with its perpendicular leads to swapping length/height in the minimum rectangle. When reconstructing rectangle corners, ensure you use unit directions and consistent projections (origin-based projections with unit vectors give clean intersections). • Special cases: Degenerate hulls with 0, 1, or 2 points require separate handling (diameter/width are 0 or the segment length). Not addressing these can cause division by zero when normalizing edge vectors.

Key Formulas

Support Function

h_{K} (u) = x \in K max ⟨ x, u ⟩

Explanation: For a unit vector u, this gives how far the convex set K extends along direction u. It is achieved at a vertex of the convex hull.

Width in Direction u

w (u) = h_{K} (u) + h_{K} (- u)

Explanation: The distance between the two support lines orthogonal to u. Use unit u to interpret this as an actual distance.

Diameter of a Convex Polygon

D = p, q \in K max ∥ p - q ∥_{2}

Explanation: The farthest pair distance equals the maximum Euclidean distance between two points in K, and it is realized by an antipodal pair.

Point-to-Line Distance

d (line (a, b), p) = \frac{∣ ( b - a ) \times ( p - a ) ∣}{∥ b - a ∥}

Explanation: Perpendicular distance from point p to the line through a and b, computed with the 2D cross product. Used for computing width against an edge.

Area of Enclosing Rectangle at Angle \theta

A (θ) = (h_{K} (u) + h_{K} (- u)) \cdot (h_{K} (v) + h_{K} (- v)), u ⊥ v, ∥ u ∥ = ∥ v ∥ = 1

Explanation: For orthonormal axes (u, v) at orientation $θ,$ the enclosing rectangle side lengths are the widths along u and v. Their product is the area.

Monotone Pointer Bound

advances \sum 1 \leq 2 n

Explanation: Each index around an n-vertex hull advances at most n times, so the total number of pointer moves across a full sweep is O(n).

Squared Distance

∥ p - q ∥_{2}^{2} = (p_{x} - q_{x})^{2} + (p_{y} - q_{y})^{2}

Explanation: Use squared distance to compare pairs without computing square roots. The argmax is the same as for Euclidean distance.

Twice Signed Triangle Area

area_2 (a, b, c) = (b - a) \times (c - a)

Explanation: This scalar is proportional to the area of triangle abc and indicates orientation. It is central to deciding pointer advancement in calipers.

Complexity Analysis

Let n be the number of input points and m the number of convex hull vertices (

m \leq n

). Computing the convex hull via Andrew’s monotone chain takes O(n log n) time and O(n) space (after sorting). All rotating calipers routines presented here run in O(m) time because each maintained pointer (antipodal, left, right, top, bottom) advances monotonically around the hull at most once per full rotation. The key invariant is that as we move from edge i to i+1 (increasing the contact angle), the extremal indices cannot move backward; therefore, the total number of index increments across the entire sweep is bounded by O(m), not O(

m^{2}

). For specific tasks: the diameter (farthest pair) sweep uses two pointers and takes O(m). The minimum width computation advances a single antipodal pointer per edge and also runs in O(m). The minimum-area rectangle uses four pointers (left, right, top, bottom) but still completes in O(m) since each pointer wraps around at most once. Space usage is O(m) to store the hull and O(1) extra for the calipers state (a constant number of indices and temporary vectors). If you build all three results from the same hull, the overall time is O(n log n + m), and the dominant factor for large inputs is typically the hull construction. Numerically, using long double and avoiding repeated square roots reduces constant factors and improves stability, but does not change asymptotic complexity.

Code Examples

Diameter of a Convex Polygon (Farthest Pair) with Rotating Calipers

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Pt {
5     long double x, y;
6     bool operator<(const Pt& other) const {
7         if (x != other.x) return x < other.x;
8         return y < other.y;
9     }
10     bool operator==(const Pt& other) const {
11         return x == other.x && y == other.y;
12     }
13 };
14 
15 static const long double EPS = 1e-12L;
16 
17 Pt operator+(const Pt& a, const Pt& b){ return {a.x + b.x, a.y + b.y}; }
18 Pt operator-(const Pt& a, const Pt& b){ return {a.x - b.x, a.y - b.y}; }
19 Pt operator*(const Pt& a, long double k){ return {a.x * k, a.y * k}; }
20 long double dot(const Pt& a, const Pt& b){ return a.x*b.x + a.y*b.y; }
21 long double cross(const Pt& a, const Pt& b){ return a.x*b.y - a.y*b.x; }
22 long double norm2(const Pt& a){ return dot(a,a); }
23 
24 // Andrew's monotone chain convex hull (removes collinear points on edges)
25 vector<Pt> convex_hull(vector<Pt> pts){
26     int n = (int)pts.size();
27     sort(pts.begin(), pts.end());
28     pts.erase(unique(pts.begin(), pts.end()), pts.end());
29     if ((int)pts.size() <= 1) return pts;
30     vector<Pt> lower, upper;
31     for (const Pt& p : pts){
32         while (lower.size() >= 2) {
33             Pt a = lower[lower.size()-2];
34             Pt b = lower[lower.size()-1];
35             if (cross(b - a, p - a) <= EPS) lower.pop_back(); else break;
36         }
37         lower.push_back(p);
38     }
39     for (int i = (int)pts.size()-1; i >= 0; --i){
40         const Pt& p = pts[i];
41         while (upper.size() >= 2) {
42             Pt a = upper[upper.size()-2];
43             Pt b = upper[upper.size()-1];
44             if (cross(b - a, p - a) <= EPS) upper.pop_back(); else break;
45         }
46         upper.push_back(p);
47     }
48     lower.pop_back(); upper.pop_back();
49     vector<Pt> hull = lower;
50     hull.insert(hull.end(), upper.begin(), upper.end());
51     return hull;
52 }
53 
54 // Rotating calipers for diameter: returns max squared distance and indices in hull
55 struct DiameterResult { long double maxDist2; int i, j; };
56 
57 DiameterResult rotating_calipers_diameter(const vector<Pt>& H){
58     int m = (int)H.size();
59     DiameterResult res{0.0L, -1, -1};
60     if (m == 0) return res;
61     if (m == 1) return {0.0L, 0, 0};
62     if (m == 2) return {norm2(H[1]-H[0]), 0, 1};
63     int j = 1;
64     for (int i = 0; i < m; ++i){
65         int ni = (i + 1) % m;
66         // Move j while area increases
67         while (fabsl(cross(H[ni] - H[i], H[(j+1)%m] - H[i])) > fabsl(cross(H[ni] - H[i], H[j] - H[i])) + EPS) {
68             j = (j + 1) % m;
69         }
70         // Update candidates (i, j) and (ni, j)
71         long double d1 = norm2(H[i] - H[j]);
72         long double d2 = norm2(H[ni] - H[j]);
73         if (d1 > res.maxDist2) res = {d1, i, j};
74         if (d2 > res.maxDist2) res = {d2, ni, j};
75     }
76     return res;
77 }
78 
79 int main(){
80     // Example polygon: a convex pentagon
81     vector<Pt> pts = { {0,0}, {3,1}, {4,4}, {1,5}, {-1,2}, {2,2} };
82     vector<Pt> H = convex_hull(pts);
83     auto ans = rotating_calipers_diameter(H);
84     cout.setf(std::ios::fixed); cout << setprecision(6);
85     cout << "Hull size: " << H.size() << "\n";
86     cout << "Max squared distance: " << (double)ans.maxDist2 << "\n";
87     if (ans.i != -1) {
88         cout << "Farthest pair indices on hull: (" << ans.i << ", " << ans.j << ")\n";
89         cout << "Points: (" << (double)H[ans.i].x << ", " << (double)H[ans.i].y << ") and ("
90              << (double)H[ans.j].x << ", " << (double)H[ans.j].y << ")\n";
91     }
92     return 0;
93 }
94

This program computes the convex hull and then applies the rotating calipers diameter sweep. It advances the antipodal index j monotonically for each edge i to find the farthest pair of vertices. Distances are compared using squared values to avoid square roots.

Time: O(n log n) for the hull + O(m) for calipersSpace: O(n)

Minimum-Area Enclosing Rectangle via Four Rotating Calipers

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Pt { long double x, y; };
5 static const long double EPS = 1e-12L;
6 
7 Pt operator+(const Pt& a, const Pt& b){ return {a.x + b.x, a.y + b.y}; }
8 Pt operator-(const Pt& a, const Pt& b){ return {a.x - b.x, a.y - b.y}; }
9 Pt operator*(const Pt& a, long double k){ return {a.x * k, a.y * k}; }
10 long double dot(const Pt& a, const Pt& b){ return a.x*b.x + a.y*b.y; }
11 long double cross(const Pt& a, const Pt& b){ return a.x*b.y - a.y*b.x; }
12 long double norm(const Pt& a){ return sqrtl(dot(a,a)); }
13 Pt perp(const Pt& a){ return {-a.y, a.x}; }
14 
15 // Minimal monotone-chain hull (removes collinear points along edges)
16 vector<Pt> convex_hull(vector<Pt> pts){
17     sort(pts.begin(), pts.end(), [](const Pt& A, const Pt& B){
18         if (A.x != B.x) return A.x < B.x;
19         return A.y < B.y;
20     });
21     pts.erase(unique(pts.begin(), pts.end(), [](const Pt& A, const Pt& B){
22         return fabsl(A.x - B.x) < EPS && fabsl(A.y - B.y) < EPS;
23     }), pts.end());
24     if (pts.size() <= 1) return pts;
25     vector<Pt> lower, upper;
26     for (auto& p : pts){
27         while (lower.size() >= 2){
28             Pt a = lower[lower.size()-2], b = lower[lower.size()-1];
29             if (cross(b-a, p-a) <= EPS) lower.pop_back(); else break;
30         }
31         lower.push_back(p);
32     }
33     for (int i = (int)pts.size()-1; i >= 0; --i){
34         Pt p = pts[i];
35         while (upper.size() >= 2){
36             Pt a = upper[upper.size()-2], b = upper[upper.size()-1];
37             if (cross(b-a, p-a) <= EPS) upper.pop_back(); else break;
38         }
39         upper.push_back(p);
40     }
41     lower.pop_back(); upper.pop_back();
42     vector<Pt> H = lower; H.insert(H.end(), upper.begin(), upper.end());
43     return H;
44 }
45 
46 struct MinRectResult {
47     long double area, width, height, angle; // angle of e_dir from x-axis (radians)
48     array<Pt,4> corners; // in CCW order starting at (left,bottom)
49 };
50 
51 MinRectResult minimum_area_rectangle(const vector<Pt>& H){
52     int m = (int)H.size();
53     MinRectResult best; best.area = numeric_limits<long double>::infinity();
54     if (m == 0){ best.area = 0; best.width = best.height = best.angle = 0; return best; }
55     if (m == 1){ best.area = 0; best.width = best.height = 0; best.angle = 0; best.corners = {H[0],H[0],H[0],H[0]}; return best; }
56     if (m == 2){
57         Pt e = {H[1].x - H[0].x, H[1].y - H[0].y};
58         long double L = norm(e);
59         Pt e_dir = {e.x / L, e.y / L}; Pt n_dir = {-e_dir.y, e_dir.x};
60         // Segment’s min-area rectangle is degenerate along the segment
61         array<Pt,4> C = { H[0], H[1], H[1], H[0] };
62         best = {0.0L, L, 0.0L, atan2l(e_dir.y, e_dir.x), C};
63         return best;
64     }
65 
66     // Initialize pointers for first edge (0->1)
67     auto unit = [&](const Pt& v){ long double L = norm(v); return Pt{v.x/L, v.y/L}; };
68     int left=0, right=0, top=0, bottom=0;
69 
70     Pt e0 = {H[1].x - H[0].x, H[1].y - H[0].y};
71     Pt e_dir = unit(e0);
72     Pt n_dir = perp(e_dir);
73 
74     auto projE = [&](int i){ return dot(H[i], e_dir); };
75     auto projN = [&](int i){ return dot(H[i], n_dir); };
76 
77     // Find initial extrema in O(m)
78     for (int i = 0; i < m; ++i){
79         if (projE(i) < projE(left)) left = i;
80         if (projE(i) > projE(right)) right = i;
81         if (projN(i) < projN(bottom)) bottom = i;
82         if (projN(i) > projN(top)) top = i;
83     }
84 
85     // Sweep over all edges
86     for (int i = 0; i < m; ++i){
87         int ni = (i + 1) % m;
88         Pt e = {H[ni].x - H[i].x, H[ni].y - H[i].y};
89         e_dir = unit(e);
90         n_dir = perp(e_dir);
91         auto projE2 = [&](int k){ return dot(H[k], e_dir); };
92         auto projN2 = [&](int k){ return dot(H[k], n_dir); };
93 
94         // Advance each pointer while its projection increases in the new frame
95         auto advMax = [&](int &idx, auto proj){ while (proj((idx+1)%m) > proj(idx) + EPS) idx = (idx+1)%m; };
96         auto advMin = [&](int &idx, auto proj){ while (proj((idx+1)%m) < proj(idx) - EPS) idx = (idx+1)%m; };
97 
98         advMin(left, projE2);
99         advMax(right, projE2);
100         advMin(bottom, projN2);
101         advMax(top, projN2);
102 
103         long double sL = projE2(left), sR = projE2(right);
104         long double tB = projN2(bottom), tT = projN2(top);
105         long double width = sR - sL;      // along e_dir
106         long double height = tT - tB;     // along n_dir
107         long double area = width * height;
108 
109         if (area < best.area - 1e-15L){
110             // Build rectangle corners: intersections of support lines
111             Pt c0 = e_dir*sL + n_dir*tB; // (left, bottom)
112             Pt c1 = e_dir*sR + n_dir*tB; // (right, bottom)
113             Pt c2 = e_dir*sR + n_dir*tT; // (right, top)
114             Pt c3 = e_dir*sL + n_dir*tT; // (left, top)
115             best.area = area; best.width = width; best.height = height;
116             best.angle = atan2l(e_dir.y, e_dir.x);
117             best.corners = {c0,c1,c2,c3};
118         }
119     }
120 
121     return best;
122 }
123 
124 int main(){
125     cout.setf(std::ios::fixed); cout << setprecision(8);
126     vector<Pt> pts = { {0,0}, {2,0}, {3,1}, {2,3}, {0,2}, {-1,1} };
127     vector<Pt> H = convex_hull(pts);
128     auto res = minimum_area_rectangle(H);
129     cout << "Hull size: " << H.size() << "\n";
130     cout << "Min area: " << (double)res.area << "\n";
131     cout << "Width (along edge dir): " << (double)res.width << ", Height (normal): " << (double)res.height << "\n";
132     cout << "Angle (radians from x-axis): " << (double)res.angle << "\n";
133     cout << "Corners (CCW):\n";
134     for (int i = 0; i < 4; ++i){
135         cout << (double)res.corners[i].x << " " << (double)res.corners[i].y << "\n";
136     }
137     return 0;
138 }
139

This code computes the convex hull and then maintains four calipers (left, right, top, bottom) aligned with the current edge and its perpendicular. For each edge, it updates indices to the extrema in the new frame using dot products onto the unit edge direction and its normal. The area, width, height, and the rectangle’s corners are computed from projections.

Time: O(n log n) for the hull + O(m) for the calipers sweepSpace: O(n)

Minimum Width of a Convex Polygon using Rotating Calipers

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Pt { long double x, y; };
5 static const long double EPS = 1e-12L;
6 
7 Pt operator-(const Pt& a, const Pt& b){ return {a.x - b.x, a.y - b.y}; }
8 long double cross(const Pt& a, const Pt& b){ return a.x*b.y - a.y*b.x; }
9 long double norm(const Pt& a){ return sqrtl(a.x*a.x + a.y*a.y); }
10 
11 // Input: convex polygon H in CCW order, with no collinear intermediates.
12 // Output: minimal width (distance between two parallel support lines)
13 long double minimum_width(const vector<Pt>& H){
14     int m = (int)H.size();
15     if (m == 0) return 0.0L;
16     if (m == 1) return 0.0L;
17     if (m == 2) return 0.0L; // any rectangle enclosing a segment can be arbitrarily thin if aligned
18 
19     long double best = numeric_limits<long double>::infinity();
20     int j = 1;
21     for (int i = 0; i < m; ++i){
22         int ni = (i + 1) % m;
23         Pt e = H[ni] - H[i];
24         long double elen = norm(e);
25         // Advance j to maximize distance to edge i->ni (antipodal to edge i)
26         while (fabsl(cross(e, H[(j+1)%m] - H[i])) > fabsl(cross(e, H[j] - H[i])) + EPS) {
27             j = (j + 1) % m;
28         }
29         long double height = fabsl(cross(e, H[j] - H[i])) / elen;
30         if (height < best) best = height;
31     }
32     return best;
33 }
34 
35 int main(){
36     cout.setf(std::ios::fixed); cout << setprecision(8);
37     vector<Pt> H = { {0,0}, {3,0}, {4,2}, {1,4}, {-1,2} }; // already convex & CCW
38     long double w = minimum_width(H);
39     cout << "Minimum width: " << (double)w << "\n";
40     return 0;
41 }
42

Given a convex polygon in CCW order, this function rotates a single caliper along each edge and advances the antipodal vertex to maximize the perpendicular distance to that edge. The minimal such distance over all edges is the polygon’s minimum width.

Time: O(m)Space: O(1)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Pt {
5	long double x, y;
6	bool operator<(const Pt& other) const {
7	if (x != other.x) return x < other.x;
8	return y < other.y;
9	}
10	bool operator==(const Pt& other) const {
11	return x == other.x && y == other.y;
12	}
13	};
14
15	static const long double EPS = 1e-12L;
16
17	Pt operator+(const Pt& a, const Pt& b){ return {a.x + b.x, a.y + b.y}; }
18	Pt operator-(const Pt& a, const Pt& b){ return {a.x - b.x, a.y - b.y}; }
19	Pt operator(const Pt& a, long double k){ return {a.x k, a.y * k}; }
20	long double dot(const Pt& a, const Pt& b){ return a.xb.x + a.yb.y; }
21	long double cross(const Pt& a, const Pt& b){ return a.xb.y - a.yb.x; }
22	long double norm2(const Pt& a){ return dot(a,a); }
23
24	// Andrew's monotone chain convex hull (removes collinear points on edges)
25	vector<Pt> convex_hull(vector<Pt> pts){
26	int n = (int)pts.size();
27	sort(pts.begin(), pts.end());
28	pts.erase(unique(pts.begin(), pts.end()), pts.end());
29	if ((int)pts.size() <= 1) return pts;
30	vector<Pt> lower, upper;
31	for (const Pt& p : pts){
32	while (lower.size() >= 2) {
33	Pt a = lower[lower.size()-2];
34	Pt b = lower[lower.size()-1];
35	if (cross(b - a, p - a) <= EPS) lower.pop_back(); else break;
36	}
37	lower.push_back(p);
38	}
39	for (int i = (int)pts.size()-1; i >= 0; --i){
40	const Pt& p = pts[i];
41	while (upper.size() >= 2) {
42	Pt a = upper[upper.size()-2];
43	Pt b = upper[upper.size()-1];
44	if (cross(b - a, p - a) <= EPS) upper.pop_back(); else break;
45	}
46	upper.push_back(p);
47	}
48	lower.pop_back(); upper.pop_back();
49	vector<Pt> hull = lower;
50	hull.insert(hull.end(), upper.begin(), upper.end());
51	return hull;
52	}
53
54	// Rotating calipers for diameter: returns max squared distance and indices in hull
55	struct DiameterResult { long double maxDist2; int i, j; };
56
57	DiameterResult rotating_calipers_diameter(const vector<Pt>& H){
58	int m = (int)H.size();
59	DiameterResult res{0.0L, -1, -1};
60	if (m == 0) return res;
61	if (m == 1) return {0.0L, 0, 0};
62	if (m == 2) return {norm2(H[1]-H[0]), 0, 1};
63	int j = 1;
64	for (int i = 0; i < m; ++i){
65	int ni = (i + 1) % m;
66	// Move j while area increases
67	while (fabsl(cross(H[ni] - H[i], H[(j+1)%m] - H[i])) > fabsl(cross(H[ni] - H[i], H[j] - H[i])) + EPS) {
68	j = (j + 1) % m;
69	}
70	// Update candidates (i, j) and (ni, j)
71	long double d1 = norm2(H[i] - H[j]);
72	long double d2 = norm2(H[ni] - H[j]);
73	if (d1 > res.maxDist2) res = {d1, i, j};
74	if (d2 > res.maxDist2) res = {d2, ni, j};
75	}
76	return res;
77	}
78
79	int main(){
80	// Example polygon: a convex pentagon
81	vector<Pt> pts = { {0,0}, {3,1}, {4,4}, {1,5}, {-1,2}, {2,2} };
82	vector<Pt> H = convex_hull(pts);
83	auto ans = rotating_calipers_diameter(H);
84	cout.setf(std::ios::fixed); cout << setprecision(6);
85	cout << "Hull size: " << H.size() << "\n";
86	cout << "Max squared distance: " << (double)ans.maxDist2 << "\n";
87	if (ans.i != -1) {
88	cout << "Farthest pair indices on hull: (" << ans.i << ", " << ans.j << ")\n";
89	cout << "Points: (" << (double)H[ans.i].x << ", " << (double)H[ans.i].y << ") and ("
90	<< (double)H[ans.j].x << ", " << (double)H[ans.j].y << ")\n";
91	}
92	return 0;
93	}
94

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Pt { long double x, y; };
5	static const long double EPS = 1e-12L;
6
7	Pt operator+(const Pt& a, const Pt& b){ return {a.x + b.x, a.y + b.y}; }
8	Pt operator-(const Pt& a, const Pt& b){ return {a.x - b.x, a.y - b.y}; }
9	Pt operator(const Pt& a, long double k){ return {a.x k, a.y * k}; }
10	long double dot(const Pt& a, const Pt& b){ return a.xb.x + a.yb.y; }
11	long double cross(const Pt& a, const Pt& b){ return a.xb.y - a.yb.x; }
12	long double norm(const Pt& a){ return sqrtl(dot(a,a)); }
13	Pt perp(const Pt& a){ return {-a.y, a.x}; }
14
15	// Minimal monotone-chain hull (removes collinear points along edges)
16	vector<Pt> convex_hull(vector<Pt> pts){
17	sort(pts.begin(), pts.end(), [](const Pt& A, const Pt& B){
18	if (A.x != B.x) return A.x < B.x;
19	return A.y < B.y;
20	});
21	pts.erase(unique(pts.begin(), pts.end(), [](const Pt& A, const Pt& B){
22	return fabsl(A.x - B.x) < EPS && fabsl(A.y - B.y) < EPS;
23	}), pts.end());
24	if (pts.size() <= 1) return pts;
25	vector<Pt> lower, upper;
26	for (auto& p : pts){
27	while (lower.size() >= 2){
28	Pt a = lower[lower.size()-2], b = lower[lower.size()-1];
29	if (cross(b-a, p-a) <= EPS) lower.pop_back(); else break;
30	}
31	lower.push_back(p);
32	}
33	for (int i = (int)pts.size()-1; i >= 0; --i){
34	Pt p = pts[i];
35	while (upper.size() >= 2){
36	Pt a = upper[upper.size()-2], b = upper[upper.size()-1];
37	if (cross(b-a, p-a) <= EPS) upper.pop_back(); else break;
38	}
39	upper.push_back(p);
40	}
41	lower.pop_back(); upper.pop_back();
42	vector<Pt> H = lower; H.insert(H.end(), upper.begin(), upper.end());
43	return H;
44	}
45
46	struct MinRectResult {
47	long double area, width, height, angle; // angle of e_dir from x-axis (radians)
48	array<Pt,4> corners; // in CCW order starting at (left,bottom)
49	};
50
51	MinRectResult minimum_area_rectangle(const vector<Pt>& H){
52	int m = (int)H.size();
53	MinRectResult best; best.area = numeric_limits<long double>::infinity();
54	if (m == 0){ best.area = 0; best.width = best.height = best.angle = 0; return best; }
55	if (m == 1){ best.area = 0; best.width = best.height = 0; best.angle = 0; best.corners = {H[0],H[0],H[0],H[0]}; return best; }
56	if (m == 2){
57	Pt e = {H[1].x - H[0].x, H[1].y - H[0].y};
58	long double L = norm(e);
59	Pt e_dir = {e.x / L, e.y / L}; Pt n_dir = {-e_dir.y, e_dir.x};
60	// Segment’s min-area rectangle is degenerate along the segment
61	array<Pt,4> C = { H[0], H[1], H[1], H[0] };
62	best = {0.0L, L, 0.0L, atan2l(e_dir.y, e_dir.x), C};
63	return best;
64	}
65
66	// Initialize pointers for first edge (0->1)
67	auto unit = [&](const Pt& v){ long double L = norm(v); return Pt{v.x/L, v.y/L}; };
68	int left=0, right=0, top=0, bottom=0;
69
70	Pt e0 = {H[1].x - H[0].x, H[1].y - H[0].y};
71	Pt e_dir = unit(e0);
72	Pt n_dir = perp(e_dir);
73
74	auto projE = [&](int i){ return dot(H[i], e_dir); };
75	auto projN = [&](int i){ return dot(H[i], n_dir); };
76
77	// Find initial extrema in O(m)
78	for (int i = 0; i < m; ++i){
79	if (projE(i) < projE(left)) left = i;
80	if (projE(i) > projE(right)) right = i;
81	if (projN(i) < projN(bottom)) bottom = i;
82	if (projN(i) > projN(top)) top = i;
83	}
84
85	// Sweep over all edges
86	for (int i = 0; i < m; ++i){
87	int ni = (i + 1) % m;
88	Pt e = {H[ni].x - H[i].x, H[ni].y - H[i].y};
89	e_dir = unit(e);
90	n_dir = perp(e_dir);
91	auto projE2 = [&](int k){ return dot(H[k], e_dir); };
92	auto projN2 = [&](int k){ return dot(H[k], n_dir); };
93
94	// Advance each pointer while its projection increases in the new frame
95	auto advMax = [&](int &idx, auto proj){ while (proj((idx+1)%m) > proj(idx) + EPS) idx = (idx+1)%m; };
96	auto advMin = [&](int &idx, auto proj){ while (proj((idx+1)%m) < proj(idx) - EPS) idx = (idx+1)%m; };
97
98	advMin(left, projE2);
99	advMax(right, projE2);
100	advMin(bottom, projN2);
101	advMax(top, projN2);
102
103	long double sL = projE2(left), sR = projE2(right);
104	long double tB = projN2(bottom), tT = projN2(top);
105	long double width = sR - sL; // along e_dir
106	long double height = tT - tB; // along n_dir
107	long double area = width * height;
108
109	if (area < best.area - 1e-15L){
110	// Build rectangle corners: intersections of support lines
111	Pt c0 = e_dirsL + n_dirtB; // (left, bottom)
112	Pt c1 = e_dirsR + n_dirtB; // (right, bottom)
113	Pt c2 = e_dirsR + n_dirtT; // (right, top)
114	Pt c3 = e_dirsL + n_dirtT; // (left, top)
115	best.area = area; best.width = width; best.height = height;
116	best.angle = atan2l(e_dir.y, e_dir.x);
117	best.corners = {c0,c1,c2,c3};
118	}
119	}
120
121	return best;
122	}
123
124	int main(){
125	cout.setf(std::ios::fixed); cout << setprecision(8);
126	vector<Pt> pts = { {0,0}, {2,0}, {3,1}, {2,3}, {0,2}, {-1,1} };
127	vector<Pt> H = convex_hull(pts);
128	auto res = minimum_area_rectangle(H);
129	cout << "Hull size: " << H.size() << "\n";
130	cout << "Min area: " << (double)res.area << "\n";
131	cout << "Width (along edge dir): " << (double)res.width << ", Height (normal): " << (double)res.height << "\n";
132	cout << "Angle (radians from x-axis): " << (double)res.angle << "\n";
133	cout << "Corners (CCW):\n";
134	for (int i = 0; i < 4; ++i){
135	cout << (double)res.corners[i].x << " " << (double)res.corners[i].y << "\n";
136	}
137	return 0;
138	}
139