Sweep Line Algorithm for Closest Pair problem

#include<bits/stdc++.h>
#define ll long long

// usage:
//      SweepLine_ClosestPair sweep;
//      sweep.init(n);
//      sweep.addPoint(id, x, y);
//      sweep.getClosestPair();
struct SweepLine_ClosestPair 
{

    struct Point {
        int idx;
        double x, y;
        
        bool operator < (Point b) const {
            if (x != b.x) 
                return x < b.x;
            else
                return y < b.y;
        }
    };
    
    Point *point;
    int n; // number of points
    
    void init(int n_) {
        n = n_;
        point = new Point[n];
    }
    
    void addPoint(int idx, double x, double y) {
        point[idx].idx = idx;
        point[idx].x = x;
        point[idx].y = y;
    }
    
    double euclidDistance(double x1, double y1, double x2, double y2) {
        return sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));
    }
    
    pair< pair<int, int>, double> getClosestPair() { // return indexes of the pair and the min distance
        
        sort(point, point + n);
        
        double min_dist = oo;
        pair<int, int> close_pair;
        
        set< pair<double, int> > activePoint; // pair <y, idx>
        activePoint.insert(make_pair(point[0].y, 0));
        
        int nearIdx = 0;
        
        for (int i = 1; i < n; ++i) {
            
            while (nearIdx < i && point[nearIdx].x < point[i].x - min_dist) {
                activePoint.erase(make_pair(point[nearIdx].y, nearIdx));
                nearIdx++;
            }
            
            for (typeof(activePoint.begin()) it = activePoint.lower_bound(make_pair(point[i].y-min_dist, 0)); 
                 it != activePoint.end() && point[it->second].y <= point[i].y + min_dist; it++ ) {
                     int id = it->second;
                     double this_dist = euclidDistance(point[i].x, point[i].y, point[id].x, point[id].y);
                     if (this_dist < min_dist) {
                         min_dist = this_dist;
                         close_pair = make_pair(point[i].idx, point[id].idx);
                     }
                 }
            
            activePoint.insert(make_pair(point[i].y, i));
        }
        
        return make_pair(close_pair, min_dist);
        
    }
    
};

Leave a Reply