#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <random>

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;
}
bool compararY(const Punto & p1, const Punto & p2) {
   return p1.second < p2.second;
}
float distanciaAlCuadradoMinima(const vector<Punto> & puntosOrdenX, const vector<Punto> & puntosOrdenY) {
   int talla = puntosOrdenX.size();
   if (talla == 2)
      return distanciaAlCuadrado(puntosOrdenX[0], puntosOrdenX[1]);
   if (talla == 3)
      return min({distanciaAlCuadrado(puntosOrdenX[0], puntosOrdenX[1]),
		  distanciaAlCuadrado(puntosOrdenX[0], puntosOrdenX[2]),
		  distanciaAlCuadrado(puntosOrdenX[1], puntosOrdenX[2])});
   int tallaIzquierda = talla / 2, tallaDerecha = talla - tallaIzquierda;
   vector<Punto> izquierdaX(tallaIzquierda), derechaX(tallaDerecha),
                 izquierdaY(tallaIzquierda), derechaY(tallaDerecha);
   for (int i = 0; i < tallaIzquierda; i++)
      izquierdaX[i] = puntosOrdenX[i];
   for (int i = 0; i < tallaDerecha; i++)
      derechaX[i] = puntosOrdenX[i + tallaIzquierda];
   for (int i = 0, j = 0, k = 0; i < talla; i++)
      if (puntosOrdenY[i] < derechaX[0])
	 izquierdaY[j++] = puntosOrdenY[i];
      else
	 derechaY[k++] = puntosOrdenY[i];
   float minima = min(distanciaAlCuadradoMinima(izquierdaX, izquierdaY),
                      distanciaAlCuadradoMinima(derechaX, derechaY));
   for (int i = 0; i < puntosOrdenY.size() - 1; i++)
      for (int j = i + 1;
           j < puntosOrdenY.size() && puntosOrdenY[j].second - puntosOrdenY[i].second < minima;
           j++)
	 minima = min(minima, distanciaAlCuadrado(puntosOrdenY[i], puntosOrdenY[j]));
   return minima;
}
float distanciaMinima(const vector<Punto> & puntos) {
   vector<Punto> puntosOrdenX(puntos), puntosOrdenY(puntos);
   sort(puntosOrdenX.begin(), puntosOrdenX.end());
   for (int i = 0; i < puntosOrdenX.size() - 1; i++)
      if (puntosOrdenX[i] == puntosOrdenX[i + 1])
	 return 0;
   sort(puntosOrdenY.begin(), puntosOrdenY.end(), compararY);
   return sqrt(distanciaAlCuadradoMinima(puntosOrdenX, puntosOrdenY));
}
int main () {

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

   vector<Punto> puntos;

   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)));
      
	 float distancia = distanciaMinima(puntos);
      
	 cout << talla << "\t" << distancia << endl;
      }

}