weird_coder @ 2020-11-23 19:41:37
#include<stdio.h>
#include<string.h>
#include<math.h>
struct node
{
double x, y;
}a[200005];
double distance(node a, node b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double min(double x,double y)
{
return x < y ? x : y;
}
node s[200005];
int cnt = 0;
double ans = 3e10;
node t[200005];
void sort(int l, int r)
{
int mid = (l + r) >> 1;
if (l >= r) return;
sort(l, mid);
sort(mid + 1, r);
int k = l;
int i = l,j=mid+1;
while (i<=mid&&j<=r)
{
if (a[i].y < a[j].y) t[k++] = a[i++];
else t[k++] = a[j++];
}
while (i <= mid) t[k++] = a[i++];
while (j <= r) t[k++] = a[j++];
for (int i = l; i <= r; i++) a[i] = t[i];
}
void sort0(int l, int r)
{
int mid = (l + r) >> 1;
if (l >= r) return;
sort(l, mid);
sort(mid + 1, r);
int k = l;
int i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (a[i].x < a[j].x) t[k++] = a[i++];
else t[k++] = a[j++];
}
while (i <= mid) t[k++] = a[i++];
while (j <= r) t[k++] = a[j++];
for (int i = l; i <= r; i++) a[i] = t[i];
}
void merge(int l, int r)
{
int mid = (l + r) >> 1;
double dis;
if (l == r) return;
if (l + 1 == r)
{
dis = distance(a[l], a[r]);
if (dis < ans) ans = dis;
return;
}
merge(l, mid);
merge(mid + 1, r);
cnt = 0;
for (int i = l; i <= r; i++)
{
if (fabs(a[i].x - a[mid].x) <= ans)
{
s[++cnt] = a[i];
}
}
sort(1, cnt);
for(int i=1;i<=cnt;i++)
for (int j = i + 1; j <= cnt && s[j].y - s[i].y < ans; j++)
{
ans = min(distance(s[i],s[j]),ans);
}
}
int main()
{
freopen("a.txt","r",stdin);
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lf%lf", &a[i].x, &a[i].y);
sort0(1, n);
merge(1, n);
printf("%.4lf", ans);
return 0;
}