← all categories

Closest Pair e891ddb2

Closest pair of points via divide and conquer. Mutates a copy (sorts it).

Time: O(n \log n). tested

content/geometry/closest-pair.h

ld closestPairRec(vector<Point> &pts, int lo, int hi) {  // pts[lo..hi) sorted by x
    if (hi - lo <= 3) {
        ld best = numeric_limits<ld>::max();
        for (int i = lo; i < hi; i++)
            for (int j = i + 1; j < hi; j++) best = min(best, (pts[i] - pts[j]).dist());
        return best;
    }

    int mid = (lo + hi) / 2;
    ld midX = pts[mid].x;
    ld best = min(closestPairRec(pts, lo, mid), closestPairRec(pts, mid, hi));

    vector<Point> strip;
    for (int i = lo; i < hi; i++) if (abs(pts[i].x - midX) < best) strip.push_back(pts[i]);
    sort(strip.begin(), strip.end(), [](Point a, Point b) { return a.y < b.y; });
    for (int i = 0; i < (int)strip.size(); i++)
        for (int j = i + 1; j < (int)strip.size() && strip[j].y - strip[i].y < best; j++)
            best = min(best, (strip[i] - strip[j]).dist());
    return best;
}

ld closestPair(vector<Point> pts) {
    sort(pts.begin(), pts.end(), [](Point a, Point b) { return a.x < b.x; });
    return closestPairRec(pts, 0, (int)pts.size());
}