//
// Implementation of your closest-pair algorithms needs to be put here.

#include <iostream>
#include <float.h>
#include "closest-pair.h"
#include "pointpair.h"
#include "sort.h"
using namespace std;
PointPair findClosestPair(int, XYPoint**, XYPoint**);
const double INF = DBL_MAX; // bigger than any possible interpoint distance

// Your naive algorithm implementation needs to replace the current method that just
// returns a point pair without any points

PointPair naiveClosestPair(int n, XYPoint* points[]) {
  PointPair closest = PointPair();
  return closest;
}

// Your divide and conquer algorithm implementation needs to replace the current method that just
// returns a point pair without any points

PointPair findClosestPair(int n, XYPoint *pointsByX[], XYPoint *pointsByY[]) {
  PointPair closest = PointPair();
  return closest;
}

//You don't need to change any of the below, but you might want to look at it so you can
//see what it is doing
//---------------------------------------------------------------------------------------
// Comparator functions for sort()

// compares p1 and p2 based on the x-coord
static bool lessThanX(const XYPoint *p1, const XYPoint *p2) { 
  return (p1->isLeftOf(p2));
}

// compares p1 and p2 based on the y-coord
static bool lessThanY(const XYPoint *p1, const XYPoint *p2) { 
  return (p1->isBelow(p2));
}

//The pre-processing for the divide-and-conquer algorithm.  You do not need
// to change this method.

PointPair fastClosestPair(int n, XYPoint* points[]) {
  XYPoint **pointsByX = new XYPoint*[n];
  XYPoint **pointsByY = new XYPoint*[n];
  for (int j = 0; j < n; j++) {
    pointsByX[j] = points[j];
    pointsByY[j] = points[j];
  }
  sort(pointsByX, n, lessThanX);       // sort by x-coord to get X
  sort(pointsByY, n, lessThanY);       // sort by y-coord to get Y
  return findClosestPair(n, pointsByX, pointsByY);
  delete [] pointsByX;   // free storage from array pointsByX of pt refs 
  delete [] pointsByY;   // free storage from array pointsByX of pt refs
}