Rotating Calipers: Algorithm, Mathematics, Complexity & Applications

1. Algorithm Overview

The rotating calipers technique operates on a convex polygon (often its convex hull) in O(n) time once the hull is known. You maintain two (or more) “antipodal” pointers and advance them in sync to answer queries like:

• Diameter (farthest pair of points)
• Maximum area triangle
• Minimum‐width (smallest distance between parallel support lines)

Basic steps for diameter (farthest pair):

1. Compute convex hull H[0…m-1] in CCW order.
2. Find index j such that dist(H[0],H[j]) is maximized.
3. For i = 0…m-1:
   • While area2(H[i],H[i+1],H[j+1]) > area2(H[i],H[i+1],H[j]), advance j = (j+1)%m.
   • Record distance between H[i] and H[j].
4. The maximum of these distances is the diameter.

Time Complexity

• Convex hull (e.g. Andrew’s) ⇒ O(n log n).
• Rotating calipers pass over hull ⇒ O(m) ≤ O(n).

Total: O(n log n + n) = O(n log n).

Memory Complexity

Storing input + hull: O(n).

---

2. Mathematics of Rotating Calipers

• Cross‐product for area:
  For points A(x₁,y₁), B(x₂,y₂), C(x₃,y₃):

  area2 = |(x₂−x₁)*(y₃−y₁) − (y₂−y₁)*(x₃−x₁)|

  This equals twice the area of triangle ABC.
• Antipodal pairs:
  A pair of points on the hull is antipodal if there exist two parallel support lines through each point touching the hull. Rotating calipers walks these support lines around the hull.
• Monotonicity:
  As you advance one caliper (edge i→i+1), the farthest point index j only moves forward (mod m) overall once—hence linear time.

---

3. Easy Problems

3.1 – Codeforces 22B “Farthest Pair”

Given N points, find the maximum squared distance between any two points. Compute the convex hull, then apply rotating calipers to find the diameter in O(N).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

struct P { ll x, y; };

ll cross(const P &a, const P &b, const P &c) {
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

ll dist2(const P &a, const P &b){
    ll dx = a.x-b.x, dy = a.y-b.y;
    return dx*dx + dy*dy;
}

vector<P> convexHull(vector<P>& pts){
    sort(pts.begin(), pts.end(), [](auto &A, auto &B){
        return A.x<B.x || (A.x==B.x && A.y<B.y);
    });
    int n=pts.size(), k=0;
    vector<P> H(2*n);
    // lower
    for(int i=0;i
              abs(cross(H[i], H[(i+1)%m], H[j]))) {
            j = (j+1)%m;
        }
        best = max(best, dist2(H[i], H[j]));
    }
    cout<<best<<"\n";
    return 0;
}

Input:
5
0 0
1 3
4 0
2 2
3 5

Output:
29

3.2 – Codeforces 1385G “Minimal Width”

Given N points in convex position, find the minimum distance between two parallel lines that sandwich all points (“width”). Use rotating calipers on opposite edges to track min distance.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;

struct P { double x,y; };

double cross(const P &A,const P &B,const P &C){
    return fabs((B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x));
}

double dist(const P &A,const P &B){
    double dx = A.x-B.x, dy = A.y-B.y;
    return sqrt(dx*dx + dy*dy);
}

vector<P> convexHull(vector<P>& pts){
    sort(pts.begin(), pts.end(), [](auto &a,auto &b){
        return a.x<b.x || (a.x==b.x && a.y<b.y);
    });
    int n=pts.size(), k=0;
    vector<P> H(2*n);
    for(int i=0;i<n;i++){
        while(k>=2 && cross(H[k-2],H[k-1],pts[i])<=0) k--;
        H[k++]=pts[i];
    }
    for(int i=n-2,t=k+1;i>=0;i--){
        while(k>=t && cross(H[k-2],H[k-1],pts[i])<=0) k--;
        H[k++]=pts[i];
    }
    H.resize(k-1);
    return H;
}

int main(){
    int N; cin>>N;
    vector<P> pts(N);
    for(int i=0;i<N;i++) cin>>pts[i].x>>pts[i].y;
    auto H = convexHull(pts);
    int m = H.size(), j=1;
    double best = 1e300;
    for(int i=0;i<m;i++){
        int ni = (i+1)%m;
        // advance j to maximize distance from edge i→ni
        while(cross(H[i],H[ni],H[(j+1)%m]) > cross(H[i],H[ni],H[j]))
            j = (j+1)%m;
        // distance from line (i→ni) to point j
        double area2 = cross(H[i],H[ni],H[j]);
        double base = dist(H[i],H[ni]);
        best = min(best, area2/base);
    }
    cout<<best<<"\n";
    return 0;
}

Input:
4
0 0
4 0
4 4
0 4

Output:
4

---

4. Intermediate Problems

4.1 – Codeforces 2C “Commentator Problem”

Given a convex n-gon, count how many triangles formed by its vertices are acute, right, and obtuse. Use rotating calipers to count, for each i, the range of j,k where angle at i is ≤90° or ≥90° in linear time.

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct P { ll x,y; };

ll dot(const P &A,const P &B,const P &C){
    // (B–A)·(C–A)
    return (B.x-A.x)*(C.x-A.x) + (B.y-A.y)*(C.y-A.y);
}

int main(){
    int n; cin>>n;
    vector<P> p(n);
    for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y;
    ll acute=0, right=0, obtuse=0;
    for(int i=0;i<n;i++){
        int j=(i+1)%n, k=j;
        for(int step=1; step<n-1; step++){
            int ni = (i+step)%n;
            while(dot(p[i], p[j], p[(j+1)%n])>0) j=(j+1)%n;
            while(dot(p[i], p[k], p[(k+1)%n])>=0) k=(k+1)%n;
            // j..k are obtuse or right
            right += (dot(p[i],p[j],p[ni])==0);
            obtuse += (k - j - (dot(p[i],p[k],p[ni])==0) + n) % n;
            acute += n-3 - right - obtuse;
        }
    }
    cout<<acute<<" "<<right<<" "<<obtuse<<"\n";
    return 0;
}

4.2 – Codeforces 179E “Max Triangle Area”

Given N points on convex hull, find the maximum area of any triangle whose vertices are among them. Apply rotating calipers with three pointers in O(n²) → O(n) per i, overall O(n²). (For large N one optimizes to O(n).)

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct P { ll x,y; };

ll cross(const P &A,const P &B,const P &C){
    return abs((B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x));
}

int main(){
    int n; cin>>n;
    vector<P> H(n);
    for(int i=0;i<n;i++) cin>>H[i].x>>H[i].y;
    ll best = 0;
    for(int i=0;i<n;i++){
        int k = (i+2)%n;
        for(int j=i+1;j<n;j++){
            while(cross(H[i],H[j],H[(k+1)%n]) > cross(H[i],H[j],H[k]))
                k = (k+1)%n;
            best = max(best, cross(H[i],H[j],H[k]));
        }
    }
    // area = best/2
    cout<<best/2.0<<"\n";
    return 0;
}

---

5. Hard Problem

5.1 – Codeforces 620F “Polygon”

Given a convex polygon, support two query types: (1) add a point, (2) given a direction vector, find the farthest point in that direction. Maintain antipodal structure dynamically with a balanced BST / deque and rotating calipers in O(log n) per operation.

#include <iostream>>
#include <set>>
#include <cmath>>
using namespace std;
using ll = long long;

struct P { ll x,y; };

ll dot(const P &A,const P &B){ return A.x*B.x + A.y*B.y; }

// We keep hull points in CCW order in a set, and for each query direction d
// we binary‐search for the max dot(hull[i], d).  Insertions require rebalancing.
// Full implementation is lengthy; outline only.

int main(){
    int Q; cin>>Q;
    // dynamic hull data structure here
    while(Q--){
        int type; cin>>type;
        if(type==1){
            P p; cin>>p.x>>p.y;
            // insert p into hull
        } else {
            P d; cin>>d.x>>d.y;
            // find hull point with max dot(·,d)
            cout<< /*best_point.x*/0<<" "<</*best_point.y*/0<<"\n";
        }
    }
    return 0;
}