Question Name:Closest pair of points problem

  
#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;
  }
      std::cout << std::fixed;

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

Problem Description

Given n points, find two points with the smallest distance to each other.

  • 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

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro