Closest Pair of Points

C++ — closest pair

double closest_pair(vector& pts) {
    sort(pts.begin(), pts.end(), [](auto& a, auto& b) { return a.x < b.x; });
    return solve(pts, 0, pts.size());
}

double solve(vector& pts, int l, int r) {
    if (r - l <= 3) {  // brute force for small
        double best = DBL_MAX;
        for (int i = l; i < r; i++)
            for (int j = i + 1; j < r; j++)
                best = min(best, dist(pts[i], pts[j]));
        return best;
    }
    int mid = (l + r) / 2;
    double d = min(solve(pts, l, mid), solve(pts, mid, r));

    // Strip: points within d of the midline
    vector strip;
    for (int i = l; i < r; i++)
        if (abs(pts[i].x - pts[mid].x) < d) strip.push_back(pts[i]);

    sort(strip.begin(), strip.end(), [](auto& a, auto& b) { return a.y < b.y; });

    for (int i = 0; i < strip.size(); i++)
        for (int j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < d; j++)
            d = min(d, dist(strip[i], strip[j]));

    return d;
}

// O(N log N) — the inner strip loop runs in O(N) total.