Solution: Closest Pair of Points

#include <iostream>
#include <float.h> // for FLT_MAX limit
#include <math.h> // for sqrt()
using namespace std;
// Structure representing a point in Euclidean Plane 
struct Point { 
	int x, y; 
}; 
// Method passed to qsort for sorting according to x
int compareXQSort(const void* a, const void* b) { 
	Point *p1 = (Point *)a, *p2 = (Point *)b; 
	return (p1->x - p2->x); 
} 
// Method passed to qsort for sorting according to y
int compareYQSort(const void* a, const void* b) { 
	Point *p1 = (Point *)a, *p2 = (Point *)b; 
	return (p1->y - p2->y); 
} 
// Returns distance of points, using distance formula
float dist(Point p1, Point p2) { 
	return sqrt( (p1.x - p2.x)*(p1.x - p2.x) + 
				(p1.y - p2.y)*(p1.y - p2.y)); 
} 
// Brute Force method to find min distance in P[n]
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; 
} 
// Returns minimum of two float values 
float min(float x, float y) { 
	return (x < y)? x : y; 
} 
/*
  Method to find distance of closest points in the strip, sorting
  it according to y-coordinates
*/
float closestInStrip(Point strip[], int size, float d) { 
	float min = d; // Initialize the minimum distance as d 
	qsort(strip, size, sizeof(Point), compareYQSort); 
  // find min distance by iterating through the points one by one
	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; 
} 
// Recursive function to find smallest distance of
// points sorted according to x-coordinates
float closestPointsRecursive(Point P[], int n) { 
	// use Brute Force for 2 or 3 points 
	if (n <= 3) 
		return bruteForce(P, n); 
	// Find mid 
	int mid = n/2; 
	Point midPoint = P[mid]; 
	// Consider the vertical line passing through the middle point 
	// calculate the smallest distance dl on left of middle point and 
	// dr on right side 
	float dl = closestPointsRecursive(P, mid); 
	float dr = closestPointsRecursive(P + mid, n-mid); 
	// Find the smaller of two distances 
	float d = min(dl, dr); 
	// Build an array strip[] that contains points close (closer than d) 
	// to the line passing through the middle point 
	Point strip[n]; 
	int j = 0; 
	for (int i = 0; i < n; i++) 
		if (abs(P[i].x - midPoint.x) < d) 
			strip[j] = P[i], j++; 
	// Find the closest points in strip. Return the minimum of d and closest 
	// distance is strip[] 
	return min(d, closestInStrip(strip, j, d) ); 
} 
// The main functin that finds the smallest distance 
// This method mainly uses closestUtil() 
float smallestDistancePair(Point P[], int n) { 
	qsort(P, n, sizeof(Point), compareXQSort); 
	// Use recursive function closestUtil() to find the smallest distance 
	return closestPointsRecursive(P, n); 
} 
// Driver program to test above functions 
int main() { 
	Point P[] = {{-2, 3}, {4, 2}, {0, 0}, {-2, -2}, {3, -1}}; 
	int n = sizeof(P) / sizeof(P[0]); 
	cout << "The smallest distance is " << smallestDistancePair(P, n); 
	return 0; 
}