//
// LAB1.CC
// Main driver code for CS 241 Lab #1.
//

#include <iostream>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include "closest-pair.h"
#include "XYpoint.h"
#include "timer.h"

using namespace std;
//===== generate a random number according to Gaussian mean 0, stdv 1 =====
//
double randGaussian() {
    double t1,t2,w;
    do {
	t1 = 2.0 * drand48() - 1.0;
	t2 = 2.0 * drand48() - 1.0;
	w = t1 * t1 + t2 * t2;
    } while (w >= 1.0);
    return t1*w;
}

static XYPoint** generateRandomPoints1(int nPoints) {
    XYPoint** points = new XYPoint*[nPoints];
    double x = 0.0;
    double y = 0.0;
    double step = sqrt(nPoints);
    for (int j = 0; j < nPoints; j++) { 
      x += 5.315*fabs(randGaussian());
      y += step * (drand48()+1);
      if (y > nPoints)
	y -= nPoints;
      points[j] =  new XYPoint((int) (x + 0.5), (int) (y + 0.5));
    }
    return points;
}

static XYPoint** generateRandomPoints2(int nPoints) {
    XYPoint** points = new XYPoint*[nPoints];
    double x = 0.0;
    double y = 0.0;
    double step = sqrt(nPoints);
    for (int j = 0; j < nPoints; j++) { 
      y += 5.315*fabs(randGaussian());
      x += step * (drand48()+1);
      if (x > nPoints)
	x -= nPoints;
      points[j] = new XYPoint((int) (x + 0.5), (int) (y + 0.5));
    }
    return points;
}

static void runAlgs(int n, XYPoint* points[]) {
  Timer timer;  

  if (n <= 20) {
    cout << "   --- The points are:" << endl;
    for (int i = 0; i < n; i++)
      cout << "         " << points[i] << endl;
    cout << endl;
  }

  PointPair closest;
  timer.start();
  closest = naiveClosestPair(n,points);
  timer.stop();
  cout << "   --- The elapsed time for the naive algorithm is ";
  cout << timer.elapsedTime() << " milliseconds," << endl;
  cout << "           and the answer is " << closest.p1() << " and " << closest.p2();
  cout << " (of distance " << closest.dist() << ")" << endl << endl;

  timer.start();
  closest = fastClosestPair(n,points);
  timer.stop();
  cout << "   --- The elapsed time for the divide and conquer algorithm is ";
  cout << timer.elapsedTime() << " milliseconds," << endl;
  cout << "           and the answer is " << closest.p1() << " and " << closest.p2();
  cout << " (of distance " << closest.dist() << ")" << endl << endl;
}

int main(int argc, char *argv[]){
  int nPoints;           // number of points
  
  // Use these lines if you want a different random set of points for each
  // run.  This code sets the seed for the RNG from the system clock time.
  //
  // NOTE: do NOT use these lines in the code you turn in.
  //
  // {
  //  time_t tp;
  //  time(&tp);
  //  seed = tp;
  // }
  
  cout << "How many points? ";
  cin >> nPoints;
  if (nPoints < 2) {
    cerr << "Error: need at least 2 points!\n";
    exit(1);
  }
  cout << "With " << nPoints << " points," << endl;
  cout << "   For the first random point generator:" << endl;
  runAlgs(nPoints,generateRandomPoints1(nPoints));
  cout << "   For the second random point generator:" << endl;
  runAlgs(nPoints,generateRandomPoints2(nPoints));
  return 0;
}