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