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