Rotating Calipers

The farthest pair of a planar point set can be found on its convex hull. Rotating calipers sweeps supporting directions around that convex boundary without checking every pair. We implement diameter: first build a strict counterclockwise hull, then advance an antipodal vertex monotonically as each edge is processed. The output keeps the maximum squared distance exact and prints its approximate square root.

Prerequisites: Andrew’s Monotone Chain; cross products; squared distances.

Build the idea

1. Reduce to extreme points

   For a fixed point, squared distance along a segment is a convex function, so its maximum occurs at an endpoint. Repeating this argument moves a maximizing pair to extreme vertices of the convex hull. Interior points cannot force a larger diameter. First use Andrew’s hull to eliminate duplicates, interior points and redundant flat boundary vertices.

2. Understand antipodal support

   For a directed hull edge i→i+1, cross(edge,p[j]−p[i]) is edge length times the perpendicular distance to its supporting line. The farthest vertex maximizes this value. The edge line and a parallel support line through that vertex touch opposite sides of the hull: an antipodal configuration. As the edge direction rotates, the opposite support position never needs to move backward.

   $$D\mathrm{²}=\max \mathrm{distance}\mathrm{²}\left(\mathrm{hull}\right[i],\mathrm{hull}[j\left]\right)$$

3. Advance the opposite vertex

   Maintain j from the previous edge. While the next vertex has strictly greater edge-triangle area, advance j cyclically. Record distances from both endpoints of the current edge to j. If the next vertex has equal area, the opposite supporting side is an edge; test it too so parallel-side ties do not lose a candidate diameter.

4. Trace a rectangle

   The hull (0,0),(3,0),(3,4),(0,4) has diameter equal to a diagonal. For the bottom edge both top corners are equally far from its line. The equality case checks both and obtains squared distance 3²+4²=25. Merely choosing one arbitrary opposite corner without consistent tie handling can miss candidates in other polygons.

5. Handle degenerate hulls and count advances

   Zero or one hull vertex gives diameter zero; two give their direct squared distance. The main caliper loop is only for h≥3. Across a full circuit, the support pointer makes O(h) forward advances, so edge processing is linear. Integer areas and squared distances fit long long under the coordinate bounds; taking absolute cross values makes the support-area intention explicit.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<iomanip>
#include<cmath>
struct Point{
    long long x,y;
    bool operator<(Point b)const{
        return x!=b.x?x<b.x:y<b.y;
    }
    bool operator==(Point b)const{
        return x==b.x&&y==b.y;
    }
};
long long cross(Point a,Point b,Point c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
std::vector<Point>hull(std::vector<Point>p){
    std::sort(p.begin(),p.end());
    p.erase(std::unique(p.begin(),p.end()),p.end());
    if(p.size()<=1){
        return p;
    }
    std::vector<Point>lower,upper;
    for(Point a:p){
        while(lower.size()>=2&&cross(lower[lower.size()-2],lower.back(),a)<=0){
            lower.pop_back();
        }
        lower.push_back(a);
    }
    for(auto it=p.rbegin();it!=p.rend();++it){
        Point a=*it;
        while(upper.size()>=2&&cross(upper[upper.size()-2],upper.back(),a)<=0){
            upper.pop_back();
        }
        upper.push_back(a);
    }
    lower.pop_back();
    upper.pop_back();
    lower.insert(lower.end(),upper.begin(),upper.end());
    return lower;
}
long long distance2(Point a,Point b){
    long long x=a.x-b.x,y=a.y-b.y;
    return x*x+y*y;
}
int main(){
    int n;
    std::cin>>n;
    std::vector<Point>p(n);
    for(auto&a:p){
        std::cin>>a.x>>a.y;
    }
    p=hull(p);
    int h=p.size();
    long long best=0;
    if(h==2){
        best=distance2(p[0],p[1]);
    }
    if(h>=3){
        int j=1;
        for(int i=0;i<h;++i){
            int next=(i+1)%h;
            auto area=[&](int k){
                return std::llabs(cross(p[i],p[next],p[k]));
            };
            // The antipodal support index only moves forward around the hull.
            while(area((j+1)%h)>area(j)){
                j=(j+1)%h;
            }
            best=std::max({best,distance2(p[i],p[j]),distance2(p[next],p[j])});
            if(area((j+1)%h)==area(j)){
                int k=(j+1)%h;
                best=std::max({best,distance2(p[i],p[k]),distance2(p[next],p[k])});
            }
        }
    }
    std::cout<<best<<'\n'<<std::fixed<<std::setprecision(6)<<std::sqrt((long double)best)<<'\n';
}

Complexity analysis

O(n log n) to build the hull, then O(h) caliper time for h extreme vertices. O(n) storage overall; O(1) extra caliper state beyond the hull. The hull stage, not the calipers, dominates unordered input.

Example input and output

Read n (0..100000), then integer points within ±10^6. Print the farthest squared distance, then its approximate square root to six decimals. Empty/singleton sets use diameter zero by convention.

Input

4
0 0
3 0
3 4
0 4

Output

25
5.000000

Either rectangle diagonal has length 5 and squared length 25.

Practical applications

Use for farthest pair and diameter. Related caliper variants solve minimum width or bounding rectangles, but require their own objective and support pointers. Closest pair is different and is not restricted to hull vertices.

Check your understanding

Why is the caliper phase O(h) rather than O(h²)?

Put it into practice

Compare against all pair distances for random small point sets.