Pagini recente » Cod sursa (job #2940048) | Cod sursa (job #2739844) | Cod sursa (job #470931) | Cod sursa (job #1434668) | Cod sursa (job #1644172)
# include <bits/stdc++.h>
# define NR 100005
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct elem {
double x, y;
}a[NR], aux[NR], var[NR];
bool cmp (elem x, elem y) {
return x.x < y.x;
}
int i,j,n,m;
double dist (elem x, elem y) {
return (x.x - y.x)*(x.x - y.x) + (x.y - y.y)*(x.y - y.y);
}
double divide (int ci, int cs) {
if (cs-ci<=2) {
double minn=INFINITY;
for (int i=ci; i<=cs; ++i)
for (int j=i+1; j<=cs; ++j)
minn=min(minn, dist(a[i], a[j]));
for (int i=ci; i<=cs; ++i) //sort cresc dupa Y
for (int j=i+1; j<=cs; ++j)
if (a[i].y < a[j].y) swap(a[i], a[j]);
return minn;
}
int mij=(ci+cs)/2;
double minn;
double DR=a[mij].x;
minn=divide (ci, mij);
minn=min(minn, divide (mij+1, cs));
int I=ci, J=mij+1, K=0, VV=0;
while (I!=mij && J!=cs) {
if (a[I].y > a[J].y) var[++K]=a[I++];
else var[++K]=a[J++];
}
while (I<=mij) var[++K]=a[I++];
while (J<=cs) var[++K]=a[J++];
for (int i=ci; i<=cs; ++i)
a[i]=var[i-ci+1];
for (int i=ci; i<=cs; ++i)
if (abs(a[i].x - DR) <= minn)
var[++VV]=a[i];
for (int i=1; i<=VV; ++i)
for (int j=i+1; j<=i+7 && j<=VV; ++j)
minn=min(minn, dist(var[i], var[j]));
return minn;
}
int main ()
{
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(7)<<sqrt(divide (1, n))<<"\n";
return 0;
}