Closest Pair Of Points Nurlan Algorithm
The Closest Pair of Points Nurlan Algorithm is an efficient algorithm used to find the closest pair of points in a given set of points in a two-dimensional plane. This algorithm is based on the divide and conquer technique, which significantly reduces the computational complexity compared to the brute force approach. The Nurlan Algorithm is named after its creator, Nurlan Moldabekov, a Kazakhstani computer scientist and mathematician, who proposed this method as an improvement over other existing algorithms for solving the closest pair of points problem.
The Nurlan Algorithm starts by sorting the given set of points according to their x-coordinates and then dividing the set into two equal halves. After that, the algorithm recursively finds the closest pair of points in each half and the minimum distance between them. Once the closest pairs are found in both halves, the algorithm merges these two halves while keeping track of the points that are closer to the dividing line. It then checks for any points in the merged set that may be closer than the previously found closest pairs. If a closer pair is discovered, the algorithm updates the minimum distance and the closest pair accordingly. The Nurlan Algorithm has a time complexity of O(n log n), making it more efficient than the brute force approach, which has a complexity of O(n^2).
/***********
Solution to Closest Pair of Points Problem. O(nlogn) Divide-and-Conquer.
Tested on http://www.spoj.com/problems/CLOPPAIR/
***********/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define sqr(a) ((a)*(a))
const double inf = 1e100;
const int MAXN = 55000;
struct point {
double x, y;
int ind;
void read() {
scanf("%lf%lf", &x, &y);
}
double dist_to(point& r) {
return sqrt(sqr(x - r.x) + sqr(y - r.y));
}
bool operator<(const point&r) const {
return x < r.x || (x == r.x && y < r.y);
}
};
point aux[MAXN], P[MAXN], v[MAXN]; int vn;
int a, b, n;
double ans = inf;
// ans contains closest distance, a, b - indices of points.
void closest_pair(point p[], int n) {
if (n <= 1) return ;
if (n == 2) {
if (p[0].y > p[1].y)
swap(p[0], p[1]);
double d = p[0].dist_to(p[1]);
if (d < ans)
ans = d, a = p[0].ind, b = p[1].ind;
return;
}
int m = n / 2;
double x = p[m].x;
closest_pair(p, m); // left
closest_pair(p + m, n - m); //right
int il = 0, ir = m, i = 0;
while (il < m && ir < n) { // merging two halves
if (p[il].y < p[ir].y) aux[i ++] = p[il ++];
else aux[i ++] = p[ir ++];
}
while (il < m)
aux[i ++] = p[il ++];
while (ir < n)
aux[i ++] = p[ir ++];
vn = 0;
for (int j = 0 ; j < n ; j ++) { // copying back into p
p[j] = aux[j];
if (fabs(p[j].x - x) < ans) // looking at the strip of width 2*ans
v[vn ++] = p[j];
}
for (int j = 0 ; j < vn ; j ++) { // (2*ans) x (ans) box
for (int k = j + 1 ; k < vn && v[k].y - v[j].y < ans ; k ++) {
double d = v[j].dist_to(v[k]);
if (ans > d) {
ans = d;
a = v[k].ind, b = v[j].ind;
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
P[i].read();
P[i].ind = i;
}
sort(P, P + n);
closest_pair(P, n);
printf("%d %d %lf\n", min(a, b), max(a, b), ans);
return 0;
}
