Pagini recente » Cod sursa (job #2200728) | Cod sursa (job #2164038) | Cod sursa (job #2671383) | Cod sursa (job #625970) | Cod sursa (job #1133012)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define nmax 100005
#define minim(a,b) (a<b)?(a):(b)
using namespace std;
struct punct {
int 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) + (a.y-b.y)*(a.y-b.y));
}
double divide(int p,int u) {
if (u-p == 1) return distanta(v[p],v[u]);
int mij = (p+u)/2;
double ds = divide(p,mij);
double dd = divide(mij+1,u);
double d = minim(ds,dd);
int i=p,j=mij+1;
while (i<mij && j < u) {
if (v[i].y <= v[j].y && i < mij) {
aux[++ap] = v[i++];
} else {
aux[++ap] = v[j++];
}
}
for (int i=p;i<=u;i++) v[i] = aux[i-p+1];
for (int i=p;i<=u;i++) {
if (abs(v[i].x-v[mij].x) <= d) {
for (int j=i+1;j<=i+8 && j<=u;j++) d = minim(d,distanta(v[i],v[p]));
}
}
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("%d %d",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
printf("%lf\n",divide(1,n));
return 0;
}