Pagini recente » Cod sursa (job #812789) | Cod sursa (job #1370649) | Cod sursa (job #1317559) | Cod sursa (job #544653) | Cod sursa (job #1614187)
#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;
}
double Distanta(Punct A, Punct B)
{ return sqrt((double)(A.x-B.x)*(A.x-B.x)+(double)(A.y-B.y)*(A.y-B.y));
}
double DI(int st, int dr)
{ int i, j;
double D=20000000000;
if (dr-st<=3)
{ for (i=st; i<dr; ++i)
for (j=i+1; j<=dr; ++j)
if (D>Distanta(a[i], a[j]))
D=Distanta(a[i], a[j]);
return D;
}
int m=(st+dr)/2;
double D1, D2;
D1=DI(st, m);
D2=DI(m, dr);
if (D1<D)
D=D1;
if (D2<D)
D=D2;
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)
if (D>Distanta(a[v[i]], a[v[j]]))
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;
}