Задача

Дано $n$ точек на плоскости, необходимо выявить пару точек, которые лежат ближе всего друг к другу.

Алгоритм решения

Разделим входные данные на левую и правую половины. Пару точек будем называть правой парой, если они принадлежат правой половине. Левой парой, если они принадлежат левой половине. Разделённой парой, если они принадлежат разным половинам.

Левую пару с минимальным расстоянием и правую пару с минимальным расстоянием найдем рекурсивными вызовами. При рекурсии базовый случай (при $кол. точек <= 3$) находим простым перебором.

Найдём расстояние между минимальной правой парой точек и минимальной левой парой точек. Выберем из них наименьшее - получим $Δ$. Будем искать точки, расстояние между которыми не больше $Δ$.

Ответом будем пара точек с минимальным расстояние из трёх найденных пар.

Псевдокод

Функция найти_лучшие_точки(точки)  
    лучшие_точки = ((INFINITY, INFINITY), (INFINITY, INFINITY))  
    минимальное_расстояние = INFINITY  
      
    Для каждой точки t1 от 0 до размера точки - 1  
        Для каждой точки t2 от 0 до размера точки - 1  
            Если t1 != t2  
                расстояние = расстояние_между(точки[t1], точки[t2])  
                  
                Если расстояние < минимальное_расстояние  
                    лучшие_точки = (точки[t1], точки[t2])  
                    минимальное_расстояние = расстояние  
  
    Вернуть лучшие_точки  
  
Функция средние_лучшие_точки(точки_x, дельта, левые_точки)  
    x_большой = левые_точки[размер левые_точки - 1][0]  
    средние_точки = пустой список  
      
    Для каждой точки точка в точки_x  
        Если (x_большой - дельта) <= точка[0] <= (x_большой + дельта)  
            Добавить точка в средние_точки  
      
    Отсортировать средние_точки по координате y  
    лучшее_расстояние = дельта  
    лучшая_пара = [(INFINITY, INFINITY), (INFINITY, INFINITY)]  
      
    Для каждой точки i от 0 до размера средние_точки - 1  
        Для каждой точки j от 0 до размера средние_точки - 1  
            Если средние_точки[i] != средние_точки[j]  
                Если расстояние_между(средние_точки[i], средние_точки[j]) < лучшее_расстояние  
                    лучшее_расстояние = расстояние_между(средние_точки[i], средние_точки[j])  
                    лучшая_пара = [средние_точки[i], средние_точки[j]]  
  
    Вернуть лучшая_пара  
  
Функция ближайшая_пара(точки_x, точки_y)  
    Если размер точки_x <= 3  
        Вернуть найти_лучшие_точки(точки_x)  
      
    левые_точки_x = точки_x[:размер точки_x // 2]  
    левые_точки_y = точки_y[:размер точки_y // 2]  
      
    правые_точки_x = точки_x[размер точки_x // 2:]  
    правые_точки_y = точки_y[размер точки_y // 2:]  
      
    левые_точки_1, левые_точки_2 = ближайшая_пара(левые_точки_x, левые_точки_y)  
    правые_точки_1, правые_точки_2 = ближайшая_пара(правые_точки_x, правые_точки_y)  
      
    дельта = минимальное значение между расстояние_между(левые_точки_1, левые_точки_2) и расстояние_между(правые_точки_1, правые_точки_2)  
      
    средние_точки_1, средние_точки_2 = средние_лучшие_точки(точки_x, дельта, левые_точки_x)  
      
    Вернуть минимум из:  
        найти_лучшие_точки([левые_точки_1, левые_точки_2]),  
        найти_лучшие_точки([правые_точки_1, правые_точки_2]),  
        найти_лучшие_точки([средние_точки_1, средние_точки_2])

Реализация на Python

Аннотация:  
find_best_points - функция находит две ближайшие точки среди заданного множества точек  
points - входной список точек  
best_points - кортеж, содержащий две ближайшие точки  
min_ - переменная, хранящая минимальное найденное расстояние  
p1 - первая точка  
p2 - вторая точка  
d - расстояние между двумя точками  
middle_best_points - функция находит две ближайшие точки в пределах полосы шириной минимального расстояния, найденного до этого этапа  
points_x - список точек, отсортированных по координате x  
delta - минимальное расстояние между парами точек  
lx - левая половина списка, отсортированного по координате x  
x_big - самая большая координата x  
middle_points - список точек, координата x которых находится в пределах полосы  
best - текущее минимальное расстояние между парами точек в полосе  
best_pair - пара точек с минимальным расстоянием в полосе  
closest_pair - функция находит две ближайшие точки в списке точек с использованием алгоритма "разделяй и властвуй"  
points_y - список точек, отсортированных по координате y  
ly - левая половина списка, отсортированного по координате y  
rx - правая половина списка, отсортированного по координате x  
ry - правая половина списка, отсортированного по координате y  
l1, l2 - пара ближайших точек в левой половине списка  
r1, r2 - пара ближайших точек в правой половине списка  
m1, m2 - Пара ближайших точек в пределах полосы

def find_best_points(points):    
    best_points = ((math.inf, math.inf), (math.inf, math.inf))    
    min_ = math.inf    
      
    for p1 in range(len(points)):    
        for p2 in range(len(points)):    
          
            if p1 != p2:    
                d = distance(points[p1], points[p2])   
                   
                if d < min_:    
                    best_points = (points[p1], points[p2])    
                    min_ = d    
  
    return best_points    
  
    
def middle_best_points(points_x, delta, lx):    
    x_big = lx[len(lx)-1][0]    
    middle_points = []    
      
    for point in points_x:    
        if (x_big - delta) <= point[0] <= (x_big + delta):    
            middle_points.append(point)    
              
    middle_points.sort(key=lambda point: point[1])    
    best = delta    
    best_pair = [(math.inf, math.inf), (math.inf, math.inf)]    
      
    for i in range(len(middle_points)):    
        for j in range(len(middle_points)):    
          
            if middle_points[i] != middle_points[j]:   
               
                if distance(middle_points[i],   
                            middle_points[j]) < best:    
                    best = distance(middle_points[i],   
                                    middle_points[j])    
                    best_pair = [middle_points[i],   
                                 middle_points[j]]    
    return best_pair  
  
  
def closest_pair(points_x, points_y):    
    if len(points_x) <= 3:    
        return find_best_points(points_x)    
    
    lx = points_x[:len(points_x)//2]    
    ly = points_y[:len(points_y)//2]    
    
    rx = points_x[len(points_x)//2:]    
    ry = points_y[len(points_y)//2:]    
    
    l1, l2 = closest_pair(lx, ly)    
    r1, r2 = closest_pair(rx, ry)    
    
    delta = min(distance(l1, l2), distance(r1, r2))    
    
    m1, m2 = middle_best_points(points_x, delta, lx)    
    return min(find_best_points([l1, l2]),   
               find_best_points([r1, r2]),    
               find_best_points([m1, m2]),    
               key=lambda point: distance(point[0], point[1]))

Олимпиадная реализация на C++

Аннотация:  
best_points - функция находит две ближайшие точки среди заданного множества точек  
points - входной список точек  
best_points - вектор точек с минимальным расстоянием между ними  
min_ - переменная, хранящая минимальное найденное расстояние  
p1 - первая точка  
p2 - вторая точка  
d - расстояние между двумя точками  
middle_best_points - функция находит две ближайшие точки в пределах полосы шириной минимального расстояния, найденного до этого этапа  
points_x - вектор точек, отсортированных по координате x  
delta - минимальное расстояние между парами точек  
lx - левая половина списка, отсортированного по координате x  
x_big - самая большая координата x  
middle_points - вектор точек, координата x которых находится в пределах полосы  
best - текущее минимальное расстояние между парами точек в полосе  
best_pair - пара точек с минимальным расстоянием в полосе  
close_pair - функция находит две ближайшие точки в списке точек с использованием алгоритма "разделяй и властвуй"  
points_y - список точек, отсортированных по координате y  
ly - левая половина списка, отсортированного по координате y  
rx - правая половина списка, отсортированного по координате x  
ry - правая половина списка, отсортированного по координате y  
l1, l2 - пара ближайших точек в левой половине списка  
r1, r2 - пара ближайших точек в правой половине списка  
m1, m2 - Пара ближайших точек в пределах полосы  
pair_points_1 - пара ближайших точек из левой половины  
pair_points_2 - пара ближайших точек из правой половины  
pair_points_3 - пара ближайших точек из полосы  
d1, d2, d3 - расстояния между ближайшими парами точек  
min_distance - минимальное расстояние между всеми найденными парами точек

typedef vector<pair<double, double>> vdd;  
typedef pair<double, double> dd;  
  
vdd best_points(vdd points) {  
  vdd best_points = {{INFINITY, INFINITY}, {INFINITY, INFINITY}};  
  double min_ = +INFINITY;  
  
  for (int p1 = 0; p1 < points.size(); p1++) {  
    for (int p2 = 0; p2 < points.size(); p2++) {  
      if (p1 != p2) {  
        double d = distance(points[p1], points[p2]);  
  
        if (d < min_) {  
          best_points = {points[p1], points[p2]};  
          min_ = d;  
        }  
      }  
    }  
  }  
  return best_points;  
}  
  
vdd mid_best_points(vdd points_x, double delta vdd lx) {  
  double x_big = lx[lx.size() - 1].first;  
  vdd mid_points;  
  
  for (dd point : points_x) {  
    if ((x_big - delta) <= point.first and point.first <= (x_big + delta))  
      mid_points.push_back(point);  
  }  
  
  sort(mid_points.begin(), mid_points.end(), compare_y);  
  double best = delta;  
  vdd best_pair = {{INFINITY, INFINITY}, {INFINITY, INFINITY}};  
  
  for (int i = 0; i < mid_points.size(); i++) {  
    for (int j = 0; j < mid_points.size(); j++) {  
      if (mid_points[i] != mid_points[j]) {  
        if (distance(mid_points[i], mid_points[j]) < best)  
  
          best = distance(mid_points[i], mid_points[j]);  
        best_pair = {mid_points[i], mid_points[j]};  
      }  
    }  
  }  
}  
  
return best_pair;  
}  
  
vdd close_pair(vdd points_x, vdd points_y) {  
  if (points_x.size() <= 3)  
    return best_points(points_x);  
  
  vdd lx, ly, rx, ry;  
  
  lx.insert(lx.end(), points_x.begin(), points_x.end() - points_x.size() / 2);  
  ly.insert(ly.end(), points_y.begin(), points_y.end() - points_y.size() / 2);  
  rx.insert(rx.end(), points_x.begin() + points_x.size() / 2, points_x.end());  
  ry.insert(ry.end(), points_y.begin() + points_y.size() / 2, points_y.end());  
  
  vdd L = close_pair(lx, ly);  
  vdd R = close_pair(rx, ry);  
  
  dd l1, l2, r1, r2, m1, m2;  
  l1 = L[0];  
  l2 = L[1];  
  r1 = R[0];  
  r2 = R[1];  
  
  double delta = min(distance(l1, l2), distance(r1, r2));  
  vdd M = mid_best_points(points_x, delta, lx);  
  m1 = M[0], m2 = M[1];  
  
  vdd pair_points_1 = best_points({l1, l2});  
  vdd pair_points_2 = best_points({r1, r2});  
  vdd pair_points_3 = best_points({m1, m2});  
  
  double d1 = distance(pair_points_1[0], pair_points_1[1]);  
  double d2 = distance(pair_points_2[0], pair_points_2[1]);  
  double d3 = distance(pair_points_3[0], pair_points_3[1]);  
  
  double min_distance = min(d3, min(d1, d2));  
  
  if (min_distance == d1) {  
    return pair_points_1;  
  }  
  
  else if (min_distance == d2) {  
    return pair_points_2;  
  }  
  
  else {  
    return pair_points_3;  
  }  
}

Продуктовая реализация на C++

Аннотация:  
find_best_points - функция находит две ближайшие точки среди заданного множества точек  
points - входной список точек  
best_points - вектор точек с минимальным расстоянием между ними  
min_ - переменная, хранящая минимальное найденное расстояние  
p1 - первая точка  
p2 - вторая точка  
d - расстояние между двумя точками  
middle_best_points - функция находит две ближайшие точки в пределах полосы шириной минимального расстояния, найденного до этого этапа  
points_x - вектор точек, отсортированных по координате x  
delta - минимальное расстояние между парами точек  
lx - левая половина списка, отсортированного по координате x  
x_big - самая большая координата x  
middle_points - вектор точек, координата x которых находится в пределах полосы  
best - текущее минимальное расстояние между парами точек в полосе  
best_pair - пара точек с минимальным расстоянием в полосе  
closest_pair - функция находит две ближайшие точки в списке точек с использованием алгоритма "разделяй и властвуй"  
points_y - список точек, отсортированных по координате y  
ly - левая половина списка, отсортированного по координате y  
rx - правая половина списка, отсортированного по координате x  
ry - правая половина списка, отсортированного по координате y  
L - пара ближайших точек в левой половине списка  
l1 - первая ближайшая точка в левой половине списка  
l2 - вторая ближайшая точка в левой половине списка  
R - пара ближайших точек в правой половине списка  
r1 - первая ближайшая точка в правой половине списка  
r2 - вторая ближайшая точка в правой половине списка  
m1 - первая ближайшая точка в пределах полосы  
m2 - вторая ближайшая точка в пределах полосы  
M - пара ближайших точек в пределах полосы  
pair_points_1 - пара ближайших точек из левой половины  
pair_points_2 - пара ближайших точек из правой половины  
pair_points_3 - пара ближайших точек из полосы  
d1, d2, d3 - расстояния между ближайшими парами точек  
min_distance - минимальное расстояние между всеми найденными парами точек

std::vector<std::pair<double, double>> find_best_points(  
    std::vector<std::pair<double, double>> points) {  
  std::vector<std::pair<double, double>> best_points = {  
      std::make_pair(INFINITY, INFINITY), std::make_pair(INFINITY, INFINITY)};  
  double min_ = +INFINITY;  
  
  for (int p1 = 0; p1 < points.size(); p1++) {  
    for (int p2 = 0; p2 < points.size(); p2++) {  
      if (p1 != p2) {  
        double d = distance(points[p1], points[p2]);  
  
        if (d < min_) {  
          best_points = {points[p1], points[p2]};  
          min_ = d;  
        }  
      }  
    }  
  }  
  return best_points;  
}  
  
std::vector<std::pair<double, double>> middle_best_points(  
    std::vector<std::pair<double, double>> points_x,  
    double delta std::vector<std::pair<double, double>> lx) {  
  double x_big = lx[lx.size() - 1].first;  
  std::vector<std::pair<double, double>> middle_points;  
  
  for (std::pair<double, double> point : points_x) {  
    if ((x_big - delta) <= point.first and point.first <= (x_big + delta))  
      middle_points.push_back(point);  
  }  
  
  std::sort(middle_points.begin(), middle_points.end(), compare_y);  
  double best = delta;  
  std::vector<std::pair<double, double>> best_pair = {  
      std::make_pair(INFINITY, INFINITY), std::make_pair(INFINITY, INFINITY)};  
  
  for (int i = 0; i < middle_points.size(); i++) {  
    for (int j = 0; j < middle_points.size(); j++) {  
      if (middle_points[i] != middle_points[j]) {  
        if (distance(middle_points[i], middle_points[j]) < best)  
  
          best = distance(middle_points[i], middle_points[j]);  
        best_pair = {middle_points[i], middle_points[j]};  
      }  
    }  
  }  
}  
  
return best_pair;  
}  
  
std::vector<std::pair<double, double>> closest_pair(  
    std::vector<std::pair<double, double>> points_x,  
    std::vector<std::pair<double, double>> points_y) {  
  if (points_x.size() <= 3)  
    return find_best_points(points_x);  
  
  std::vector<std::pair<double, double>> lx, ly, rx, ry;  
  
  lx.insert(lx.end(), points_x.begin(), points_x.end() - points_x.size() / 2);  
  ly.insert(ly.end(), points_y.begin(), points_y.end() - points_y.size() / 2);  
  rx.insert(rx.end(), points_x.begin() + points_x.size() / 2, points_x.end());  
  ry.insert(ry.end(), points_y.begin() + points_y.size() / 2, points_y.end());  
  
  std::vector<std::pair<double, double>> L = closest_pair(lx, ly);  
  std::vector<std::pair<double, double>> R = closest_pair(rx, ry);  
  
  std::pair<double, double> l1, l2, r1, r2, m1, m2;  
  l1 = L[0];  
  l2 = L[1];  
  r1 = R[0];  
  r2 = R[1];  
  
  double delta = std::min(distance(l1, l2), distance(r1, r2));  
  std::vector<std::pair<double, double>> M =  
      middle_best_points(points_x, delta, lx);  
  m1 = M[0], m2 = M[1];  
  
  std::vector<std::pair<double, double>> pair_points_1 =  
      find_best_points({l1, l2});  
  std::vector<std::pair<double, double>> pair_points_2 =  
      find_best_points({r1, r2});  
  std::vector<std::pair<double, double>> pair_points_3 =  
      find_best_points({m1, m2});  
  
  double d1 = distance(pair_points_1[0], pair_points_1[1]);  
  double d2 = distance(pair_points_2[0], pair_points_2[1]);  
  double d3 = distance(pair_points_3[0], pair_points_3[1]);  
  
  double min_distance = std::min(d3, std::min(d1, d2));  
  
  if (min_distance == d1) {  
    return pair_points_1;  
  }  
  
  else if (min_distance == d2) {  
    return pair_points_2;  
  }  
  
  else {  
    return pair_points_3;  
  }  
}