Closest Pair of Points — Divide and Conquer

The closest pair asks for the minimum distance among all distinct input entries. Checking all pairs costs O(n²), which is too slow for large sets. Divide and conquer restricts cross-boundary comparisons to a narrow strip and uses a packing argument to keep them linear per recursion level. The implementation maintains y-order during merging, achieving actual O(n log n) time rather than repeatedly sorting strips.

Prerequisites: Vectors, squared distance, sorting, divide and conquer, merge sort.

Build the idea

1. Divide once in x-order

   Sort points by x then y. A recursive range initially contains an x-contiguous subset. Split it by index and capture splitX before either child rearranges its range. Each child returns its smallest squared distance and leaves that child range sorted by y. The minimum child answer is the current bound d²; only a pair crossing the partition can improve it.

2. Restrict possible improvements

   If a cross-boundary pair has distance below d, both points lie within d of the dividing vertical line. Therefore ignore points whose squared horizontal offset is at least d². Merge the two child y-sorted ranges in linear time using a shared buffer, then traverse the strip in this y-order. For each point, only earlier strip points with vertical separation below the current d need checking.

   $$T\left(n\right)=2T(n/2)+O\left(n\right)$$

3. Explain the constant candidate bound

   Within either child, distinct points are separated by at least the child minimum, hence at least the initial d. Partition a strip window of width 2d and height d into a constant number of small cells; two points from the same child cannot occupy a cell whose diameter is less than d. This packing bounds candidates by a constant, commonly expressed as at most seven following neighbors with careful boundary conventions. The code uses the equivalent y-gap stopping rule.

4. Preserve the merge invariant

   Base cases of at most three points check every pair and sort that tiny range by y. After children return, std::merge writes into buffer, then copies back. The buffer is reused for strip points only after the merged order has been restored in points. Sorting the entire strip separately at each call would add a logarithmic factor and violate the claimed recurrence.

5. Trace duplicates and a small example

   For (0,0),(5,0),(2,1),(3,1), the closest pair is (2,1),(3,1), squared distance 1. Duplicate coordinates from different entries validly give distance zero; once best is zero no strictly improving candidate exists and strip work stops. Squared comparisons remain exact under ±10^6 coordinate bounds. Only the final square root is approximate.

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

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
struct Point{
    long long x,y;
};
long long distance2(Point a,Point b){
    long long x=a.x-b.x,y=a.y-b.y;
    return x*x+y*y;
}
bool byY(Point a,Point b){
    return a.y!=b.y?a.y<b.y:a.x<b.x;
}
std::vector<Point>points,buffer;
long long solve(int left,int right){
    if(right-left<=3){
        long long best=4000000000000000000LL;
        for(int i=left;i<right;++i){
            for(int j=i+1;j<right;++j){
                best=std::min(best,distance2(points[i],points[j]));
            }
        }
        std::sort(points.begin()+left,points.begin()+right,byY);
        return best;
    }
    int mid=(left+right)/2;
    long long splitX=points[mid].x; // Capture before recursion reorders by Y.
    long long best=std::min(solve(left,mid),solve(mid,right));
    std::merge(points.begin()+left,points.begin()+mid,points.begin()+mid,points.begin()+right,
        buffer.begin()+left,byY);
    std::copy(buffer.begin()+left,buffer.begin()+right,points.begin()+left);
    int count=0;
    for(int i=left;i<right;++i){
        long long dx=points[i].x-splitX;
        if(dx*dx>=best){
            continue;
        }
        for(int j=count-1;j>=0;--j){
            long long dy=points[i].y-buffer[left+j].y;
            if(dy*dy>=best){
                break;
            }
            best=std::min(best,distance2(points[i],buffer[left+j]));
        }
        buffer[left+count++]=points[i];
    }
    return best;
}
int main(){
    int n;
    std::cin>>n;
    points.resize(n);
    buffer.resize(n);
    for(auto&p:points){
        std::cin>>p.x>>p.y;
    }
    std::sort(points.begin(),points.end(),[](Point a,Point b){
        return a.x!=b.x?a.x<b.x:a.y<b.y;
    });
    long long answer=solve(0,n);
    std::cout<<answer<<'\n'
                <<std::fixed<<std::setprecision(6)<<std::sqrt((long double)answer)<<'\n';
}

Complexity analysis

O(n log n) total time: initial sort plus linear merge/strip work at each logarithmic level. O(n) shared buffer/point storage and O(log n) recursion stack. A constant-sized base sort does not add a logarithmic factor.

Example input and output

Read n (2..200000), then integer points within ±10^6; repeated coordinates are allowed. Print the minimum squared distance and its approximate square root to six decimals.

Input

4
0 0
5 0
2 1
3 1

Output

1
1.000000

The final two points are one unit apart; every other pair is farther.

Practical applications

Use for nearest sensor pairs, collision proximity and geometric separation. A spatial grid can be fast under additional assumptions; this divide-and-conquer algorithm gives a deterministic O(n log n) bound. Diameter instead uses hulls and rotating calipers.

Check your understanding

Why must the recursion return each range in y-order?

Put it into practice

Compare with all-pairs distances on random sets, including duplicates and equal x-values.