#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

#define point pair<int, int> 

// Calculate the Euclidean distance between two points
double distance(pair<point, point> points)
{
  double ret = (points.first.first - points.second.first) *
    (points.first.first - points.second.first) +
    (points.first.second - points.second.second) *
    (points.first.second - points.second.second);
  return sqrt(ret);
}

// Find the pair of points in vector points after start but strictly before
// end, and return that pair. 
pair<point, point > closestPair(vector<point > points, int start, int end)
{
  // Base case
  if (end - start <= 2) 
    return pair<point, point>(points[start], points[start + 1]);

  // Now there are 3 possibilities: 
  // Left holds the smallest distance
  // Right holds the smallest distance
  // The best actually span the distance
  pair<point, point> left = closestPair(points, start, (end + start) / 2);
  pair<point, point> right = closestPair(points, (end + start) / 2, end);
  pair<point, point> best;


  if (distance(left) < distance(right))
    {
      best = left;
    } 
  else
    {
      best = right;
    }

  // Loop through those pairs of points that could possibly span the 
  // gap and be better than what we've found.
  int delta = (int)(distance(best) + 0.99999);
  for (int i = (end + start) / 2 - delta; i < (end + start) / 2 + delta; i++)
    {      
      for (int j = i + 1; j < i + delta && j < (end + start) / 2 + delta; j++)
	{	
	  // If we find something else, update our best and 
	  // our knowledge of how far apart things can be (Thus how far
	  // we much search.)
	  pair<point, point> middle(points[i], points[j]);      
	  if (distance(middle) < distance(best))
	    {
	      best = middle;
	      delta = (int)(distance(best) + 0.99999);
	    }
	}
    }
  return best;

}

int main()
{
  // Set up some points
  vector<point > points;
  for (int i = 0; i < 32; i++)
    {
      points.push_back(point(i, rand() % 40));
      cout << points[i].first << " " << points[i].second << endl;
    }

  pair<point, point > ret = closestPair(points, 0, 32);
  
  cout << "The closest two points are " 
       << ret.first.first << ", " << ret.first.second << " and " 
       << ret.second.first << ", " << ret.second.second << endl;
}