Pagini recente » Cod sursa (job #539234) | Cod sursa (job #2569676) | Cod sursa (job #860808) | Cod sursa (job #529460) | Cod sursa (job #1201258)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAX 100005
const long long INF=1ll<<62;
struct punct
{
int x, y;
}v[MAX];
bool cmp(punct a, punct b){return a.x < b.x;}
int y[MAX], aux[MAX];
long long solve(int st, int dr);
long long dist(punct a, punct b);
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
int i, n;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d%d",&v[i].x,&v[i].y);
y[i]=i;
}
sort(v+1,v+n+1,cmp);
printf("%f",sqrt((double)solve(1,n)));
return 0;
}
long long solve(int st, int dr)
{
int mij, k, i, j;
long long d, ds, dd;
if(st+1==dr)
{
if(v[st].y > v[dr].y){y[st]=dr; y[dr]=st;}
return dist(v[st],v[dr]);
}
if(st == dr)
return INF;
mij = (st+dr)/2;
d=solve(st, mij);
dd=solve(mij+1,dr);
if(d > dd) d = dd;
k=0;
while(i<=mij and j<=dr)
{
if(v[y[i]].y < v[y[i]].y) aux[++k] = y[i++];
else aux[++k] = y[j++];
}
while(i<=mij) aux[++k] = y[i++];
while(j<=dr) aux[++k] = y[j++];
for(i=st; i<=dr; i++)
y[i] = aux[i-st+1];
k=0;
for(i=st; i<=dr; i++)
if(abs(v[mij].x - v[y[i]].x) <= d)
aux[++k] = y[i];
for(i=1; i<k; i++)
for(j=1; j<8 && i+j<=k; j++){
dd = dist(v[aux[i]], v[aux[i+j]]);
if(d>dd and dd!=0) d = dd;
}
return d;
}
long long dist(punct a, punct b)
{
return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y);
}