# 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);

}

};
```