Question Name: Closest Pair of Points -

  
#include <iostream> 
#include <float.h> 
#include <stdlib.h> 
#include <math.h> 
#include <iomanip>

using namespace std; 
  
struct Point 
{ 
    int x, y; 
}point[10]; 
  
  

int compareX(const void* a, const void* b) 
{ 
    Point *p1 = (Point *)a,  *p2 = (Point *)b; 
    return (p1->x - p2->x); 
} 
int compareY(const void* a, const void* b) 
{ 
    Point *p1 = (Point *)a,   *p2 = (Point *)b; 
    return (p1->y - p2->y); 
} 
  
float dist(Point p1, Point p2) 
{ 
    return sqrt( (p1.x - p2.x)*(p1.x - p2.x) + 
                 (p1.y - p2.y)*(p1.y - p2.y) 
               ); 
} 
  

float bruteForce(Point P[], int n) 
{ 
    float min = FLT_MAX; 
    for (int i = 0; i < n; ++i) 
        for (int j = i+1; j < n; ++j) 
            if (dist(P[i], P[j]) < min) 
                min = dist(P[i], P[j]); 
    return min; 
} 
  
float min(float x, float y) 
{ 
    return (x < y)? x : y; 
} 
  
  

float stripClosest(Point strip[], int size, float d) 
{ 
    float min = d; 
  
   
    for (int i = 0; i < size; ++i) 
        for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) 
            if (dist(strip[i],strip[j]) < min) 
                min = dist(strip[i], strip[j]); 
  
    return min; 
} 
  

float closestUtil(Point Px[], Point Py[], int n) 
{ 
    if (n <= 3) 
        return bruteForce(Px, n); 
  
    int mid = n/2; 
    Point midPoint = Px[mid]; 
  
  
   
    Point Pyl[mid+1]; 
    Point Pyr[n-mid-1];  
    int li = 0, ri = 0;  
    for (int i = 0; i < n; i++) 
    { 
      if (Py[i].x <= midPoint.x) 
         Pyl[li++] = Py[i]; 
      else
         Pyr[ri++] = Py[i]; 
    } 

    float dl = closestUtil(Px, Pyl, mid); 
    float dr = closestUtil(Px + mid, Pyr, n-mid); 
  
    float d = min(dl, dr); 
  
  
    Point strip[n]; 
    int j = 0; 
    for (int i = 0; i < n; i++) 
        if (abs(Py[i].x - midPoint.x) < d) 
            strip[j] = Py[i], j++; 

    return min(d, stripClosest(strip, j, d) ); 
} 
  

float closest(Point P[], int n) 
{ 
    Point Px[n]; 
    Point Py[n]; 
    for (int i = 0; i < n; i++) 
    { 
        Px[i] = P[i]; 
        Py[i] = P[i]; 
    } 
  
    qsort(Px, n, sizeof(Point), compareX); 
    qsort(Py, n, sizeof(Point), compareY); 
  
    return closestUtil(Px, Py, n); 
} 
  
int main() 
{ 
    int n,i;
  float awm;
  cin>>n;
  for(i=0;i<n;i++) { 
    cin>>point[i].x>>point[i].y;
  }
    cout << "The smallest distance is " ;
      std::cout << std::fixed;

 std:: cout<<std::setprecision(6);
  cout<<closest(point, n); //aviraj
 
    return 0; 
}

Problem Description

A typical Divide and Conquer algorithm solves a problem using following three steps.

1. Divide: Break the given problem into subproblems of same type.
2. Conquer: Recursively solve these subproblems
3. Combine: Appropriately combine the answers

Closest Pair of Points The problem is to find the closest pair of points in a set of points in x-y plane. The problem can be solved in O(n^2) time by calculating distances of every pair of points and comparing the distances to find the minimum.

The Divide and Conquer algorithm solves the problem in O(nLogn) time.

Test Case 1

Input (stdin)

Expected Output

The smallest distance is 3.605551

Test Case 2

Input (stdin)

Expected Output

The smallest distance is 1.414214