Pagini recente » Cod sursa (job #3274624) | Cod sursa (job #2176849) | Cod sursa (job #3281916) | Cod sursa (job #1159702) | Cod sursa (job #408229)
Cod sursa(job #408229)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define file_in "cmap.in"
#define file_out "cmap.out"
#define x first
#define y second
#define pdd pair<double,double>
#define Nmax 122212
struct punct
{
int x,y;
};
int N;
punct v[Nmax];
punct p[Nmax];
double dist(punct a, punct b)
{
return sqrt((double)((long long)((long long)a.x-b.x)*(a.x-b.x)+(long long)((long long)a.y-b.y)*(a.y-b.y)));
}
int cmp(punct a, punct b)
{
return a.x<b.x;
}
double dmin(int st, int dr)
{
int mij=(st+dr)>>1;
double m=p[mij].x;
if (st>=dr)
return 100000000.0;
if (st==dr-1)
{
if (p[st].y>p[dr].y)
{
double aux;
aux=p[st].y;
p[st].y=p[dr].y;
p[dr].y=aux;
}
return dist(p[st],p[dr]);
}
double d1=dmin(st,mij);
double d2=dmin(mij+1,dr);
double d=min(d1,d2);
int i1=st;
int i2=mij+1;
int i=st-1;
while(i1<=mij && i2<=dr)
if (p[i1].y<=p[i2].y) v[++i]=p[i1++];
else v[++i]=p[i2++];
while(i1<=mij) v[++i]=p[i1++];
while(i2<=dr) v[++i]=p[i2++];
int nr=0;
for(i=st;i<=dr;++i)
{
p[i]=v[i];
if (abs(p[i].x-m)<=d) v[++nr]=p[i];
}
double q=100000000.0;
int j;
for(i=1;i<=nr;++i)
for(j=i-1;j>=i;--j)
q=min(q,dist(v[i],v[j]));
return min(q,d);
}
int main()
{
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d", &N);
for (int i=1;i<=N;++i)
scanf("%d %d", &p[i].x, &p[i].y);
sort(p+1,p+N+1,cmp);
//for (int i=1;i<=N;++i) printf("%d %d\n", p[i].x, p[i].y);
double sol=dmin(1,N);
printf("%.6lf\n", sol);
fclose(stdin);
fclose(stdout);
return 0;
}