Pagini recente » Cod sursa (job #2164119) | Cod sursa (job #2038251) | Cod sursa (job #2790920) | Cod sursa (job #615735) | Cod sursa (job #1614141)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
struct Punct
{ int x, y;
} a[100001];
int n, v[100001];
ifstream f("cmap.in");
ofstream g("cmap.out");
inline bool cmp(const Punct &a, const Punct &b)
{ if (a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
float Distanta(Punct A, Punct B)
{ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
float DI(int st, int dr)
{ int i, j;
float D=Distanta(a[st], a[dr]);
if (dr-st<=3)
{ for (i=st; i<dr; ++i)
for (j=i+1; j<=dr; ++j)
D=min(D, Distanta(a[i], a[j]));
return D;
}
int m=(st+dr)/2;
D=min(DI(st, m), DI(m, dr));
int nr=0;
for (i=m; i>=st && a[m].x-a[i].x<=D; --i)
v[++nr]=i;
for (i=m+1; i<=dr && a[i].x-a[m].x<=D; ++i)
v[++nr]=i;
sort(v+1, v+nr+1);
for (i=1; i<=nr; ++i)
for (j=i+1; j<=nr && j<=i+7; ++j)
D=min(D, Distanta(a[v[i]], a[v[j]]));
return D;
}
int main()
{ int i;
f>>n;
for (i=1; i<=n; ++i)
f>>a[i].x>>a[i].y;
sort(a+1, a+n+1, cmp);
g<<fixed<<setprecision(6)<<DI(1, n);
return 0;
}