Pagini recente » Cod sursa (job #2711306) | Cod sursa (job #364749) | Cod sursa (job #1188236) | Cod sursa (job #271553) | Cod sursa (job #1133041)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define nmax 100005
#define minim(a,b) (a<b)?(a):(b)
using namespace std;
struct punct {
long long x,y;
};
punct v[nmax];
punct aux[nmax];
int ap;
int n;
bool cmp(punct a,punct b) {
if (a.x < b.x) return true;
else if (a.x == b.x) return a.y < b.y;
else return false;
}
inline 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 divide(int p,int u) {
if (u-p <= 3) {
double d = distanta(v[p],v[u]);
for (int i=p;i<u;i++) for (int j=i+1;j<=u;j++) d = minim(d,distanta(v[i],v[j]));
return d;
}
int mij = (p+u)/2;
double ds = divide(p,mij);
double dd = divide(mij,u);
double d = minim(ds,dd);
int i=p,j=mij+1; ap = 0;
while (i<=mij && j<=u) {
if (v[i].y >= v[j].y) aux[++ap] = v[i++];
else aux[++ap] = v[j++];
}
for (;i<=mij;i++) aux[++ap] = v[i];
for (;j<=u;j++) aux[++ap] = v[j];
for (int i=p;i<=u;i++) v[i] = aux[i-p+1];
for (register int i=p;i<u;i++) {
if (abs(v[i].x-v[mij].x) <= d && i!=mij) {
for (int j=i+1;v[j].y-v[i].y <= d && j<=u;j++) d = minim(d,distanta(v[i],v[j]));
}
}
return d;
}
int main() {
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lld %lld",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
printf("%lf\n",divide(1,n));
return 0;
}