Pagini recente » Cod sursa (job #561179) | Cod sursa (job #1350771) | Cod sursa (job #1946842) | Cod sursa (job #362579) | Cod sursa (job #2174137)
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#define N 100005
using namespace std;
struct punct
{
int x, y;
}v[N], a[N];
int n;
long long dmax, INF;
void citire()
{
scanf("%d\n", &n);
for(int i=0;i<n;i++)
scanf("%d %d\n", &v[i].x, &v[i].y);
}
long long dist(punct e, punct f)
{
return 1LL*(e.x-f.x)*(e.x-f.x)+1LL*(e.y-f.y)*(e.y-f.y);
}
int cmp(punct e, punct f)
{
return (e.x<f.x || e.x==f.x && e.y<f.y);
}
void interclasare(int st, int mij, int dr)
{
int k=-1, i, j;
for(i=st, j=mij+1;i<=mij && j<=dr;)
if(cmp(v[i], v[j]))
a[++k]=v[i++];
else
a[++k]=v[j++];
while(i<=mij)
a[++k]=v[i++];
while(j<=dr)
a[++k]=v[j++];
for(i=dr;i>=st;i--, k--)
v[i]=a[k];
}
long long divide(int st, int dr)
{
int nr=0;
long long min=INF;
if(dr-st<3)
{
for(int i=st;i<dr;i++)
for(int j=i+1;j<=dr;j++)
{
long long d=dist(v[i], v[j]);
if(min>d)
min=d;
}
sort(v+st, v+dr+1, cmp);
return min;
}
int mij=(st+dr)/2;
long long d1=divide(st, mij);
long long d2=divide(mij+1, dr);
if(d1>d2)
d1=d2;
min=d1;
interclasare(st, mij, dr);
for(int i=st;i<=dr;i++)
if(dist(v[i], v[mij])<=d1)
a[nr++]=v[i];
for(int i=0;i<nr;i++)
for(int j=i+1;j<nr && j<=i+7;j++)
{
long long d=dist(a[i], a[j]);
if(d<min)
min=d;
}
return min;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
citire();
INF=dist(v[0], v[1]);
sort(v, v+n, cmp);
dmax=divide(0, n-1);
printf("%.6llf\n", sqrt(dmax));
return 0;
}