Why this matters when you build with AI
Ask an AI tool for the farthest pair of points and you often get two nested loops over all pairs. That is O(n^2) work, which is fine for 1000 points and too slow for 200000. The code passes the sample, and the timeout appears only on the large hidden test. The fix is to take the convex hull first, which the previous lesson builds, and then walk around it once.
The second common failure is in the pointer walk itself. A tool that knows the idea of rotating calipers often resets the pointer to the start for every edge, or starts it at corner 0 without checking the first step. Both produce code that looks right and gives wrong answers on some inputs. This lesson shows a wrong start that fails on a 7-point input, and it gives a brute force you can run to catch the bug.
Terms used here
A convex hull is the smallest convex polygon around a point set, and its corners are the points where the boundary turns. Lesson 05 builds it with the monotone chain. This lesson uses that code with collinear points removed, so each corner appears once.
A supporting line of a polygon is a line that touches the polygon and leaves all of it on one side. An edge of a convex polygon lies on a supporting line. A width of a point set in a direction is the distance between two supporting lines that are parallel to that direction. The minimum width is the smallest of these over all directions.
Rotating calipers is the name for a family of methods that use two pointers, or two parallel lines, that turn around a convex polygon the way the arms of a caliper turn around a shape. The name was coined by Toussaint in 1983. The idea is older: Shamos described the antipodal pairs of a convex polygon in his 1978 Yale dissertation.
An antipodal pair is two corners that each lie on a supporting line, where the two lines are parallel. Picture a rectangle around a convex shape: its two opposite sides touch two corners of the shape, and those two corners are an antipodal pair.
The idea: a pointer that only moves forward
Take the hull as corners h[0] to h[m-1], listed counterclockwise (CCW). Each edge goes from h[i] to h[i+1], with indices taken modulo m. For each edge, define its far corner as the corner farthest from the line through the edge. The farthest pair of points is one of the pairs made from an edge and its far corner, and the same idea gives the minimum width.
The far corner can be found by walking. Start with the pointer j at some corner. For the current edge, compare the cross product of the edge with the corner after j against the cross product with j. The cross product is cross(a, b, c) as defined in lesson 01, and for a fixed edge it grows with distance from the line. If the next corner gives a larger value, advance j. If not, stop.
Worked example
Take the hull of five points, (-1,2), (0,0), (4,0), (5,2) and (2,4). The lowest-leftmost point is (-1,2), so it is h[0], and the corners run counterclockwise from there. The program's trace mode prints the pointer for every edge, from the real run:
edge 0: (-1,2)->(0,0) j 1 -> 3, far vertex (5,2)
edge 1: (0,0)->(4,0) j 3 -> 4, far vertex (2,4)
edge 2: (4,0)->(5,2) j 4 -> 0, far vertex (-1,2)
edge 3: (5,2)->(2,4) j 0 -> 1, far vertex (0,0)
edge 4: (2,4)->(-1,2) j 1 -> 2, far vertex (4,0)For edge 0, the pointer starts at corner 1, which is the end of the edge, and walks forward to corner 3, (5,2). Corner 3 is the farthest from the line through (-1,2) and (0,0). You can check this by hand. The line has direction (1,-2), and the cross product of that direction with a point (x,y) is 2x + y up to the constant offset. Its values are 8 for (4,0), 12 for (5,2) and 8 for (2,4), so (5,2) is the largest.
Look at the sequence of pointer positions: 3, 4, 0, 1, 2. It moves forward around the hull and wraps from 4 back to 0 at the end. It never goes back to a corner it already passed, so the whole walk is one lap of the hull with a little extra.
Why the pointer only moves forward
Walk along the hull and look at the direction of each edge. Going counterclockwise around a convex polygon, the direction of each edge turns counterclockwise by a positive angle, and the total turn over all edges is exactly one full turn, 360 degrees. The edge directions therefore appear in a fixed order around the circle, once each.
The far corner for an edge is the corner where a line parallel to that edge touches the hull on the far side. Its position is set by the direction of the edge alone. When the edge turns counterclockwise, the parallel line that touches the hull turns with it, and the touching corner moves counterclockwise too. A corner that has been passed by the touching line is never touched again during the same lap, because that would require the direction to turn through a full circle. So the pointer can be advanced without ever going back.
That argument gives a bound. Over the whole loop, j moves about one lap, so the calipers cost O(m) after the hull. The hull costs O(n log n) to build, and that cost dominates.
Diameter: the farthest pair
The farthest pair of a point set always has both points on the hull, so the search can stay on the corners. The squared distance |p - q|^2 is a convex function of p when q is fixed, and the maximum of a convex function over a convex polygon is reached at a corner. So the farthest point from any q is a corner, and the pair can be taken from corners.
It is also known that the farthest pair is an antipodal pair. This is the result that Shamos and Toussaint used. The calipers test, for each edge, the far corner and the corner after it, and the endpoints of the edge against both. Taking both j and j+1 covers the case where two corners are the same distance from an edge, which happens when an edge is parallel to a diagonal. The brute-force test below checks this case too.
For the worked example, the squared distances between corner pairs give the answer. The pair (-1,2) and (5,2) is 6 apart on a horizontal line, so its squared distance is 36. The other pairs are smaller: (4,0) to (-1,2) is 29, (5,2) to (0,0) is 29, and (0,0) to (2,4) is 20. So the diameter squared is 36.
Exact squared distances matter. A squared distance is an integer when the coordinates are integers. With coordinates up to 10^9, the largest squared distance is (2*10^9)^2 + (2*10^9)^2 = 8*10^18, which fits in a signed 64-bit integer, but a double holds integers exactly only up to about 9*10^15, so a double would round the answer. The farthest-pair code below uses long long throughout.
Minimum width
For a convex polygon, the width in a direction is the largest distance between two corners measured across that direction. A standard fact about convex polygons is that the minimum width is reached in a direction perpendicular to an edge. So it is enough to check each edge: for the edge, find the far corner and take its distance from the edge line. The smallest such distance over all edges is the minimum width.
Take the triangle (0,0), (4,0), (0,3). Its edges have lengths 4, 3 and 5. The distance from the far corner to the edge of length 4 is 3, to the edge of length 3 is 4, and to the hypotenuse of length 5 is 12/5 = 2.4. The minimum is 2.4, and the program prints 2.400000000. You can check this with the altitude formula: the altitude to the hypotenuse is 4 * 3 / 5.
The code keeps the best edge as a fraction, the cross product c over the squared edge length L, because the distance is c / sqrt(L). Comparing c^2 / L values without division needs products of the form c^2 * L. With coordinates up to 10^4, c is at most 8*10^8, c^2 at most 6.4*10^17, and the product with L at most 5.12*10^26. That fits in __int128, which holds about 1.7*10^38. The final value is printed as a long double. For larger coordinates, the same comparison needs a bigger integer type.
The full program
This program is the one tested below. Its three modes are diameter, width and trace. The hull is the corner-only version from lesson 05.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Pt {
ll x, y;
};
bool operator<(const Pt& a, const Pt& b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool operator==(const Pt& a, const Pt& b) {
return a.x == b.x && a.y == b.y;
}
ll cross(const Pt& o, const Pt& a, const Pt& b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
// Corner points only (collinear points dropped), counterclockwise.
// Same function as in the convex hull lesson, with keep_collinear = false.
vector<Pt> convex_hull(vector<Pt> p) {
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
int n = p.size();
if (n <= 1) return p;
bool all_collinear = true;
for (int i = 1; i + 1 < n && all_collinear; i++)
if (cross(p[0], p[n - 1], p[i]) != 0) all_collinear = false;
if (all_collinear) return {p[0], p[n - 1]};
vector<Pt> h(2 * n);
int k = 0;
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;
h[k++] = p[i];
}
for (int i = n - 2, lower = k + 1; i >= 0; i--) {
while (k >= lower && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;
h[k++] = p[i];
}
h.resize(k - 1);
return h;
}
ll dist2(const Pt& a, const Pt& b) {
ll dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}
// Farthest pair, exact squared distance. Coordinates up to 1e9 in
// absolute value keep dist2 <= 8e18, which fits in a signed 64-bit integer.
ll diameter2(const vector<Pt>& h) {
int m = h.size();
if (m == 1) return 0;
if (m == 2) return dist2(h[0], h[1]);
ll best = 0;
int j = 1;
for (int i = 0; i < m; i++) {
const Pt& a = h[i];
const Pt& b = h[(i + 1) % m];
// The vertex farthest from the line a-b is reached by walking forward.
while (cross(a, b, h[(j + 1) % m]) > cross(a, b, h[j])) j = (j + 1) % m;
int j1 = (j + 1) % m;
best = max({best, dist2(a, h[j]), dist2(b, h[j]), dist2(a, h[j1]), dist2(b, h[j1])});
}
return best;
}
// Minimum width: for each edge, the largest distance from the edge line to a
// vertex. Coordinates up to 1e4 keep every value below 2^127, so the
// comparison of fractions is exact with __int128.
long double min_width(const vector<Pt>& h) {
int m = h.size();
if (m <= 2) return 0;
ll bestC = -1, bestL = 1;
int j = 1;
for (int i = 0; i < m; i++) {
const Pt& a = h[i];
const Pt& b = h[(i + 1) % m];
while (cross(a, b, h[(j + 1) % m]) > cross(a, b, h[j])) j = (j + 1) % m;
ll c = cross(a, b, h[j]); // twice the triangle area, so the height is c / |ab|
ll L = dist2(a, b);
// Compare c^2 / L with bestC^2 / bestL without division.
if (bestC < 0 || (__int128)c * c * bestL < (__int128)bestC * bestC * L) {
bestC = c;
bestL = L;
}
}
return (long double)bestC / sqrtl((long double)bestL);
}
int main(int argc, char** argv) {
string mode = argc > 1 ? argv[1] : "diameter";
int n;
if (scanf("%d", &n) != 1) return 1;
vector<Pt> p(n);
for (auto& q : p)
if (scanf("%lld %lld", &q.x, &q.y) != 2) return 1;
vector<Pt> h = convex_hull(p);
if (mode == "diameter") {
printf("%lld\n", diameter2(h));
} else if (mode == "width") {
printf("%.9Lf\n", min_width(h));
} else if (mode == "trace") {
// Prints the pointer position for each edge, to check that j only moves forward.
int m = h.size();
int j = 1;
for (int i = 0; i < m; i++) {
const Pt& a = h[i];
const Pt& b = h[(i + 1) % m];
int start = j;
while (cross(a, b, h[(j + 1) % m]) > cross(a, b, h[j])) j = (j + 1) % m;
printf("edge %d: (%lld,%lld)->(%lld,%lld) j %d -> %d, far vertex (%lld,%lld)\n", i, a.x, a.y, b.x,
b.y, start, j, h[j].x, h[j].y);
}
}
return 0;
}Compile it and run each mode:
g++ -std=c++17 -O2 -Wall -Wextra -o rc rc06.cpp
./rc diameter < sample.txt
./rc width < sample.txt
./rc trace < sample.txtThe sample file for the worked example holds five lines after the count: 5, then 0 0, 4 0, 5 2, 2 4, -1 2. The trace above was printed from that input.
Three checks on the real runs. The triangle (0,0), (4,0), (0,3) gives a diameter squared of 25, which is the squared hypotenuse. The triangle's width is 2.400000000, as computed above. The four points (0,0), (1,1), (2,2) and (3,3) lie on one line, so the hull has two corners, and the diameter squared is 18.
How it was tested
I compiled the program with g++ -std=c++17 -O2 -Wall -Wextra on g++ 15.2.0, and every output in this lesson comes from those runs.
The diameter and width were checked against brute force on 1500 random small cases. The brute force for the diameter takes the maximum squared distance over all pairs of input points. The brute force for the width takes all pairs of input points as a line, measures the spread of the points across that line, which is the largest signed distance minus the smallest, and keeps the smallest spread over all pairs. It uses Fraction arithmetic, so it does not round. The coordinates were between -10 and 10, and 457 of the cases were on one line. All 1500 matched on both quantities. The width test accepted a difference below 1e-6 between the program's decimal and the exact value.
The diameter was also checked on 200 random cases with 2 to 40 points and coordinates up to 10^9, against the all-pairs brute force, and all matched. A run on 200000 random points with coordinates up to 10^9 took about 0.04 seconds of wall time, and it printed a diameter squared of 7962938117472929236. Your timing will differ by machine.
Testing the width brute force found a mistake in my own first version. It measured the largest absolute distance from a line rather than the spread. On the 7-point set (4,2), (1,4), (2,-1), (1,-4), (0,-2), (1,4), (-3,-1), the wrong brute printed 3.287979746, while the program and the corrected brute both give 4.919349550. The wrong value is smaller than the true minimum width, so it could not be a width at all. Measuring only one side of a line gives a number that is not a width, and the brute force uses the full spread for that reason.
Common mistakes
Starting the pointer at corner 0. I ran a version with j = 0 at the start, and it printed 130 for this 7-point input, where the correct diameter squared is 146:
-5 6
1 -3
-1 -3
0 -5
-2 -5
-6 -4
-2 3The far pair is (-5,6) and (0,-5), whose squared distance is 25 + 121 = 146. With j = 0, the first edge starts at a corner that gives both sides a cross of zero, so the pointer never moves on that edge. The walk then misses the far corner. The fix is to start j at 1, which is the corner after the first edge's start, and let the loop advance it.
Taking the wrong measure for the width. The symptom is the 3.287979746 value above, which is smaller than the true minimum width. The width of a direction is a spread, not a single distance from a line. For a hull edge, all corners lie on one side, so the largest distance from the edge line already is the spread, but only for hull edges.
Forgetting the wrap-around. The pointer goes from index m-1 back to 0. Writing j + 1 without % m reads past the end of the vector. I did not run this one, so I cannot show the exact symptom, but the read is out of bounds and the output can change from run to run.
Using doubles for squared distances. Two squared distances near 8*10^18 differ by a small amount that a double cannot store, since a double holds all integers exactly only up to about 9*10^15. Use long long for squared distances, and use double only for the final printed decimal.
Forgetting the small hulls. A hull with one corner has diameter 0 and width 0. A hull with two corners is a segment, whose width is 0 and whose diameter is its squared length. The code handles both before the loop, because the loop assumes at least three corners.
Prompt for checking AI-written calipers code
Here is my C++17 function for the farthest pair of points, using rotating calipers over a convex hull with corners in counterclockwise order. Check the pointer start, the wrap-around with modulo, the case of one, two and collinear points, and whether the answer is exact for coordinates up to 1e9. Compare it with an O(n^2) brute force on 500 random inputs with 3 to 8 points each, then on 200 inputs with coordinates up to 1e9. Show the inputs that failed, if any, with the expected and actual outputs, and say which tests you did not run.A good answer starts the pointer after the first edge, uses modulo on every index, returns 0 or the segment length for one or two corners, uses long long for squared distances, and shows the outputs of its own brute-force run. Check the answer by running the 7-point input above: the correct diameter squared is 146, and a version that prints 130 has the pointer bug.
Checklist
- Build the hull first, with collinear points removed, and handle one and two corners before the loop.
- Start the pointer at corner 1, and advance it while the next corner gives a larger cross product.
- Use
% mon every index. - Take the farthest corner and its neighbor against both ends of each edge.
- Keep squared distances as
long long, and use__int128only where the bound on the product has been checked. - Test against an all-pairs brute force on small random inputs, including collinear and repeated points.
Exercise on your own machine
Write a program that reads N and then N points, and prints the squared distance of the farthest pair using the calipers. Then write the all-pairs version, and compare the two on 1000 random inputs with 2 to 10 points and coordinates between -5 and 5. Next, run both on 200000 random points with coordinates up to 10^9, but compare only the calipers' output with a second calipers implementation written differently, because the all-pairs version will not finish. Record the time and say which machine you used.
Summary
After the hull, the calipers walk around it with one pointer that never moves back, because the far corner for each edge turns counterclockwise with the edge direction. That gives the diameter and the minimum width in linear time. The diameter is an exact integer when coordinates are integers and squared distances stay below about 9*10^18. The width needs a fraction comparison, which __int128 handles for coordinates up to 10^4. The most common bug is the wrong pointer start, and the test that catches it is a brute force on small random inputs.
Practice problems
Each practice input can be checked with the program above. Try each problem first, then open the answer.
-
Square. The input is 4 points:
(0,0),(3,0),(3,3)and(0,3). Find the squared diameter.Show the answer
18The diagonal is from
(0,0)to(3,3), and its squared length is9 + 9 = 18. -
Right triangle. The input is 3 points:
(0,0),(5,0)and(0,12). Find the squared diameter.Show the answer
169The hypotenuse has length 13, so its squared length is 169. The other two sides have squared lengths 25 and 144, which are smaller.
-
Rectangle width. The input is 4 points:
(0,0),(4,0),(4,2)and(0,2). Find the minimum width withwidthmode.Show the answer
2.000000000The shorter side of the rectangle is 2, and a rectangle's width across its short side is its smallest width.
-
All on one line. The input is 4 points:
(0,0),(1,1),(2,2)and(3,3). Find the squared diameter.Show the answer
18The hull is the segment from
(0,0)to(3,3), with two corners. Its squared length is 18. -
Why the pointer must not move back. Explain, without code, why resetting the pointer to corner 1 for each edge makes the calipers slower but not wrong, and why starting it at corner 0 can make the answer wrong.
Show the answer
Resetting to corner 1 walks the hull again for every edge, which gives O(m^2) time instead of O(m). It is still correct, because the walk from corner 1 reaches the far corner for each edge. Starting at corner 0 is wrong because the first edge starts at a corner whose cross product with the edge is zero, so the advance test sees no gain and the pointer stays put. The 7-point input above gives 130 instead of 146 for that reason.