Pagini recente » Cod sursa (job #975691) | Cod sursa (job #3165096) | Cod sursa (job #3241833) | Cod sursa (job #1358458) | Cod sursa (job #599273)
Cod sursa(job #599273)
#include<stdio.h>
#include<vector>
#include<algorithm>
#define pb push_back
#include<math.h>
#define LMAX 100100
#define INF 1<<30
using namespace std;
struct pozdy
{
int x,y;
} x[LMAX];
inline bool comp1(pozdy A,pozdy B)
{
return A.x<B.x;
}
inline bool comp2(pozdy A,pozdy B)
{
return A.y<B.y;
}
double dist(pozdy A,pozdy B)
{
return sqrt((double)(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double divide(int st,int dr)
{
if(st>=dr)
return INF;
if(dr-st==1)
return dist(x[st],x[dr]);
int m=(st+dr)>>1;
double d1=divide(st,m),d2=divide(m+1,dr),D;
if(d1<d2)
D=d1;
else
D=d2;
vector<pozdy> X;
int i=m,j;
while(x[m].x-x[i].x<=D && i>=st)
X.pb(x[i]),i--;
i=m+1;
while(x[i].x-x[m].x<=D && i<=dr)
X.pb(x[i]),i++;
sort(X.begin(),X.end(),comp2);
int l=X.size();
for(i=0;i<l;i++)
for(j=i+1;j<=l && j-i<=6;j++)
if(dist(X[i],X[j])<D)
D=dist(X[i],X[j]);
return D;
}
int main()
{
int n,i;
double D;
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&x[i].x,&x[i].y);
sort(x+1,x+n+1,comp1);
D=divide(1,n);
printf("%.6lf",D);
return 0;
}