#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <random>
#include <iomanip> // setprecision
#include <ctime>   // clock_gettime

using namespace std;
typedef pair<float, float> Punto;

float distanciaAlCuadrado(const Punto & p1, const Punto & p2) {

   float a = p2.first  - p1.first;
   float b = p2.second - p1.second;
   return a * a + b * b;

}

float distanciaMinimaFuerzaBruta(const vector<Punto> & puntos) {

   if (puntos.size() < 2)
      throw string("Necesitamos al menos dos puntos.");

   float minima = distanciaAlCuadrado(puntos[0], puntos[1]);

   for (int i = 0; i < puntos.size() - 1; i++)
      for (int j = i + 1; j < puntos.size(); j++)
	 minima = min(minima,
		      distanciaAlCuadrado(puntos[i], puntos[j]));
  
   return sqrt(minima);
      
}

bool compararY(const Punto & p1, const Punto & p2) {

   return p1.second < p2.second;

}

float distanciaAlCuadradoMinima(const vector<Punto> & puntosPorX,
                                const vector<Punto> & puntosPorY) {

   // Si estamos en el caso base de la recursion, terminamos

   int talla = puntosPorX.size();

   if (talla == 2)
      return distanciaAlCuadrado(puntosPorX[0], puntosPorX[1]);

   if (talla == 3)
      return min({distanciaAlCuadrado(puntosPorX[0], puntosPorX[1]),
		  distanciaAlCuadrado(puntosPorX[0], puntosPorX[2]),
		  distanciaAlCuadrado(puntosPorX[1], puntosPorX[2])});
    
   // Dividimos los puntos ordenados por X entre la mitad izquierda y la mitad derecha sin perder esa ordenacion

   int tallaIzquierda = talla / 2;

   vector<Punto> puntosIzquierdaPorX(puntosPorX.begin(), puntosPorX.begin() + tallaIzquierda),
                 puntosDerechaPorX(puntosPorX.begin() + tallaIzquierda, puntosPorX.end());

   // Repartimos los puntos ordenados por Y entre la mitad izquierda y la mitad derecha sin perder esa ordenacion

   vector<Punto> puntosIzquierdaPorY(tallaIzquierda),
                 puntosDerechaPorY(talla - tallaIzquierda);

   for (int i = 0, j = 0, k = 0; i < talla; i++)
      if (puntosPorY[i] < puntosDerechaPorX[0]) // A igual X mira Y; no pueden coincidir X e Y
	 puntosIzquierdaPorY[j++] = puntosPorY[i];
      else
	 puntosDerechaPorY[k++] = puntosPorY[i];

   // Llamamos a la funcion recursiva pasandole los puntos de la mitad izquierda ordenados por X y ordenados por Y

   float minimaIzquierda = distanciaAlCuadradoMinima(puntosIzquierdaPorX, puntosIzquierdaPorY);

   // Llamamos a la funcion recursiva pasandole los puntos de la mitad derecha ordenados por X y ordenados por Y

   float minimaDerecha = distanciaAlCuadradoMinima(puntosDerechaPorX, puntosDerechaPorY);

   // Creamos un vector con los puntos en la franja central ordenados por Y

   float minima = min(minimaIzquierda, minimaDerecha);
   vector<Punto> puntosCentralesPorY;
   float frontera = puntosIzquierdaPorX[tallaIzquierda - 1].first;
   for (auto p : puntosPorY)
      if ( abs(frontera - p.first)  < minima )
	 puntosCentralesPorY.push_back(p);

   // Calculamos distancias entre puntos de la franja central con criterio de parada por distancia vertical

   for (int i = 0; i < puntosCentralesPorY.size() - 1; i++)
      for (int j = i + 1;
           j < puntosCentralesPorY.size() && puntosCentralesPorY[j].second - puntosCentralesPorY[i].second < minima;
           j++)
	 minima = min(minima,
		      distanciaAlCuadrado(puntosCentralesPorY[i], puntosCentralesPorY[j]));

   return minima;
      
}

float distanciaMinimaDivideYVenceras(const vector<Punto> & puntos) {

   if (puntos.size() < 2)
      throw string("Necesitamos al menos dos puntos.");

   // Creamos una copia del vector de puntos ordenada por X y, en caso de empate en X, por Y

   vector<Punto> puntosPorX(puntos);

   sort(puntosPorX.begin(), puntosPorX.end()); // Usamos operator< de pair para ordenar por X y, en caso de empate, por Y

   // Detectamos duplicados y terminamos si los hay
   // Gracias a la ordenacion anterior, si hay dos puntos consecutivos iguales devolvemos 0,
   // y si no los hay en adelante sabremos que no hay ningun par de puntos iguales

   for (int i = 0; i < puntosPorX.size() - 1; i++)
      if (puntosPorX[i] == puntosPorX[i + 1])
	 return 0;

   // Creamos una copia del vector de puntos ordenada por Y

   vector<Punto> puntosPorY(puntos);

   sort(puntosPorY.begin(), puntosPorY.end(), compararY); // Aqui basta ordenar solo por Y

   // Llamamos a la funcion recursiva pasandole las dos copias ordenadas

   return sqrt(distanciaAlCuadradoMinima(puntosPorX, puntosPorY));

}


double segundosDiferencia(timespec inicio, timespec fin) {
   const double nano = 1e9;
   return ( (fin.tv_sec + fin.tv_nsec / nano) - (inicio.tv_sec + inicio.tv_nsec / nano) );
}

int main () {

   default_random_engine default_random;
   uniform_real_distribution<float> generadorAleatorio(-1000.0, 1000.0);

   timespec tiempoInicial, tiempoFinal;

   vector<Punto> puntos;

   cout << fixed << setprecision(10);

   for (int talla = 2, tallaMax = 10; tallaMax <= 100000; tallaMax *= 10)
    
      for (; talla < tallaMax; talla += tallaMax / 10) {
      
	 while(puntos.size() < talla)
	    puntos.push_back(Punto(generadorAleatorio(default_random), generadorAleatorio(default_random)));

	 clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoInicial);
	 float distancia1 = distanciaMinimaFuerzaBruta(puntos);
	 clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoFinal);
	 double tiempoSolucionFuerzaBruta = segundosDiferencia(tiempoInicial, tiempoFinal);


	 clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoInicial);
	 float distancia2 = distanciaMinimaDivideYVenceras(puntos);
	 clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoFinal);
	 double tiempoSolucionDivideYVenceras = segundosDiferencia(tiempoInicial, tiempoFinal);


	 if (distancia1 != distancia2) {
	    cout << "ERROR." << endl;
	    return EXIT_FAILURE;
	 } else {
	    cout << talla << "\t" << tiempoSolucionFuerzaBruta << "\t" << tiempoSolucionDivideYVenceras << endl;
	    return 0; 
	 }
      }

}