#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <list>
#include <vector>
#include <utility>
#include <cmath>
#include <cfloat>
using namespace std;
ifstream f("cmap.in");
FILE *g;
struct Point
{
int x,y;
};
int CompareX(const void *A, const void *B)
{
Point *a = (Point *)A;
Point *b = (Point *)B;
return (a->x - b->x);
}
int CompareY(const void *A, const void *B)
{
Point *a = (Point *)A;
Point *b = (Point *)B;
return (a->y - b->y);
}
double Distance(Point A, Point B)
{
return sqrt((A.x - B.x)*(A.x - B.x)*1.0 +
(A.y - B.y)*(A.y - B.y)*1.0);
}
pair<double, pair<Point, Point> > DistanceFor3OrLessPoints(Point points[], int nrPoints)
{
pair<double, pair<Point, Point> > result;
result.first = DBL_MAX;
double newDistance;
for (int i = 0; i < nrPoints-1; i++)
for (int j = i+1; j < nrPoints; j++)
if ((newDistance = Distance(points[i],points[j])) < result.first)
{
result.first = newDistance;
result.second.first = points[i];
result.second.second = points[j];
}
return result;
}
pair<double, pair<Point, Point> > PickBestPair(pair<double, pair<Point, Point> > A, pair<double, pair<Point, Point> > B)
{
return (A.first < B.first)? A : B;
}
pair<double, pair<Point, Point> > MinOnStrip(Point strip[], int sizeOfStrip, pair<double, pair<Point, Point> > smallestDistance)
{
pair<double, pair<Point, Point> > result = smallestDistance;
double newDistance;
for (int i = 0; i < sizeOfStrip-1; i++)
for (int j = i+1; j < sizeOfStrip && (strip[j].y - strip[i].y) < result.first; j++)
if ((newDistance = Distance(strip[i], strip[j])) < result.first)
{
result.first = newDistance;
result.second.first = strip[i];
result.second.second = strip[j];
}
return result;
}
pair<double, pair<Point, Point> > FindClosestPairOfPoints(Point pointsX[], Point pointsY[], int nrPoints)
{
pair<double, pair<Point, Point> > result;
if (nrPoints <= 3)
return DistanceFor3OrLessPoints(pointsX,nrPoints);
else
{
int middlePointPosition = nrPoints/2;
Point middlePoint = pointsX[middlePointPosition];
Point leftSidePoints[middlePointPosition + 1];
Point rightSidePoints[nrPoints - middlePointPosition - 1];
int leftPosition = 0;
int rightPosition = 0;
for (int i = 0; i < nrPoints; i++)
{
if (pointsY[i].x <= middlePoint.x)
{
leftSidePoints[leftPosition++] = pointsY[i];
}
else
{
rightSidePoints[rightPosition++] = pointsY[i];
}
}
pair<double, pair<Point, Point> > smallestDistanceLeft = FindClosestPairOfPoints(pointsX,
leftSidePoints,
middlePointPosition);
pair<double, pair<Point, Point> > smallestDistanceRight = FindClosestPairOfPoints(pointsX + middlePointPosition,
rightSidePoints,
nrPoints - middlePointPosition);
pair<double, pair<Point, Point> > smallestDistance = PickBestPair(smallestDistanceLeft,
smallestDistanceRight);
Point strip[nrPoints];
int nrPointsOnStrip = 0;
for (int i = 0; i< nrPoints; i++)
{
if (abs(pointsY[i].x - middlePoint.x) < smallestDistance.first)
{
strip[nrPointsOnStrip] = pointsY[i];
nrPointsOnStrip++;
}
}
return PickBestPair(smallestDistance, MinOnStrip(strip, nrPointsOnStrip, smallestDistance));
}
}
int main() {
int nrPoints;
Point point;
f>>nrPoints;
Point pointsX[nrPoints];
Point pointsY[nrPoints];
for (int i = 0; i < nrPoints; i++)
{
f>>point.x>>point.y;
pointsX[i] = point;
pointsY[i] = point;
}
qsort(pointsX, nrPoints, sizeof(Point), CompareX);
qsort(pointsY, nrPoints, sizeof(Point), CompareY);
pair<double, pair<Point, Point> > result = FindClosestPairOfPoints(pointsX, pointsY, nrPoints);
//g<<"A("<<result.second.first.x<<", "<<result.second.first.y<<")\n";
//g<<"B("<<result.second.second.x<<", "<<result.second.second.y<<")\n";
//g<<"Distance between A and B: "<<result.first<<'\n';
g = fopen ("cmap.out","w");
fprintf(g, "%.6f",result.first);
//g<<result.first;
f.close();
fclose(g);
return 0;
}