Question Name:Mutual Smallest Distance

#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); 
  
    // Find the middle point 
    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;
  }
      std::cout << std::fixed;

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

Problem Description

Given n points in d-dimensions, find two
whose mutual distance is smallest.

• Test Case 1

  Input (stdin)
  

  4
  10 20
  5 1 
  2 10
  3 4

  Expected Output
  

  3.605551

• Test Case 2

  Input (stdin)
  

  6
  2 3
  12 30
  40 50
  5 1 
  12 10
  3 4

  Expected Output
  

  1.414214