#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int n;
const long long INF = 1e18;
struct point{
long long x,y;
}v[100005],aux[100005],ind[100005];
/*
idea:
1. sort points by x
2. start splitting in divide and conquer fashion
3. when you get to 2 or 3 points just manually compute min distance between all pairs
4. !! recursing up: !!
suppose on the left side we have the set of points Pl and on the right Pr
all we know is min distance between any pair of 2 points on the left and separately on the right
recall our target is min distance between any 2 points of the whole set
so we can literally verify if the total minimum improves by left_min or right_min
now, do we really need to check all the possible pair of points from the left and right ?
answer is a happy no
we only need to check the pairs of points that might have the chance to result in a smaller distance
than our current d_min
question is what points are those?
suppose P1(x1,y1) belongs to left half and P2(x2,y2) belongs to right half
recall distance formula d = sqrt ( ( x1 - x2 ) ^ 2 + ( y1 - y2 ) ^ 2 )
if abs(x1 - x2) >= d_min this will already result in a final distance d >= d_min
same happends if abs(y1 - y2) >= d_min
so we literally must only check the pair of points that satisfy simultaneously:
| x2 - x1 | < d_min
| y2 - y1 | < d_min
now if we get the dividing mid line between the 2 zones ( given by mean of x values of
the rightmost point in the left and leftmost point on the right )
we can also automatically tell that we only consider the points on the left that satisfy:
mid - d_min <= x1 <= mid
and on the right that satisfy: mid <= x2 <= mid + d_min
because otherwise they would directly have a greater distance than d_min no matter what the
other point in the pair is.
now for any 2 points on the same side we know that the min distance between any 2 is
at most d_min ( both on the left and on the right ) !!!
thus in a square of d_min x d_min there can be exactly 4 points ( all in the corners ) for this to be preserved
lets take all the points that satisfy the x condition ( both on the left and the right ) call this set P
now sort P by y
so any 2 consecutive points in this P set either are on the same side and their distance is >= d_min
or one is on the left and one is on the right, case in which the distance could be smaller
interesting part is this: say we are now on a point Pl(xl,yl)
all points on the left must be positioned above yl + d_min clearly
but the same thing happends on the right, consider a point on the right Pr(xr,yr)
If it indeed is at a smaller distance than d_min to P1, it also imposes the same distance upwards to the next
point of yr + d_min.
Worst case of this is when all points are situated right in the rectangle corners with one corner in P1 or P2
now the distance between all these points is d_min and they are 8 ( 4 on the left, 4 on the right and 2 are
identical right on the dividing line )
nice
*/
long long calc_dist2(struct point p1, struct point p2)
{
return (p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y);
}
int cmp_x(const void *a, const void *b)
{
const struct point *p = a, *q = b;
return (p->x > q->x) - (p->x < q->x);
}
void swap(int l,int r)
{
v[l].y ^= v[r].y;
v[r].y ^= v[l].y;
v[l].y ^= v[r].y;
v[l].x ^= v[r].x;
v[r].x ^= v[l].x;
v[l].x ^= v[r].x;
}
long long min2(long long a,long long b)
{
if(a>b)
return b;
return a;
}
void merge_sides(int l1, int r1,int l2, int r2)
{
int i = l1, j = l2, k = 0;
while(i <= r1 && j <= r2)
{
if(v[i].y < v[j].y)
{
aux[++k] = v[i];
i++;
}
else if(v[i].y > v[j].y)
{
aux[++k] = v[j];
j++;
}
else
{
aux[++k] = v[i];
i++;
aux[++k] = v[j];
j++;
}
}
while(i <= r1)
{
aux[++k] = v[i];
i++;
}
while(j <= r2)
{
aux[++k] = v[j];
j++;
}
for(int i=1,j=l1;i<=k;i++,j++)
v[j] = aux[i];
}
long long solve(int l, int r)
{
if(l >= r)
return INF;
if(r-l+1 == 2)
{
if(v[l].y > v[r].y)
swap(l,r);
return calc_dist2(v[l],v[r]);
}
if(r-l+1 == 3)
{
if(v[l].y > v[r].y)
swap(l, r);
if(v[l].y > v[l+1].y)
swap(l, l+1);
if(v[l+1].y > v[r].y)
swap(l+1, r);
long long d1 = calc_dist2(v[l], v[l+1]);
long long d2 = calc_dist2(v[l+1], v[r]);
long long d3 = calc_dist2(v[l], v[r]);
return min2(min2(d1,d2),d3);
}
int mid = (l+r)/2;
long long midx = (v[mid].x + v[mid+1].x) / 2;
long long min_left = solve(l, mid);
long long min_right = solve(mid+1, r);
long long d_min = min2(min_left, min_right);
merge_sides(l,mid,mid+1,r);
int k = 0;
for(int i=l;i<r;i++)
if( ( midx <= v[i].x && v[i].x - midx <= d_min) || (midx >= v[i].x && midx - v[i].x <= d_min))
ind[++k] = v[i]; // only points closer than d_min to the dividing line
for(int i=1;i<=k;i++)
for(int j=1;j<8 && i+j <=k;j++)
d_min = min2(d_min,calc_dist2(ind[i],ind[i+j]));
return d_min;
}
int main()
{
FILE *fin = fopen("cmap.in","r");
FILE *fout = fopen("cmap.out", "w");
fscanf(fin, "%d", &n);
for(int i=1;i<=n;i++)
{
fscanf(fin, "%lld", &v[i].x);
fscanf(fin, "%lld", &v[i].y);
}
qsort(v+1, n, sizeof(struct point), cmp_x);
fprintf(fout, "%.6f", sqrt( solve(1,n) ) );
fclose(fin);
return 0;
}