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)

      4
      10 20
      5 1 
      2 10
      3 4
      

      Expected Output

      The smallest distance is 3.605551
  • Test Case 2

    Input (stdin)

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

    Expected Output

    The smallest distance is 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