Pagini recente » Cod sursa (job #1075915) | Cod sursa (job #900329) | Cod sursa (job #529942) | Cod sursa (job #1166686) | Cod sursa (job #2061005)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("cmap.in");
ofstream fo("cmap.out");
int n;
struct PUNCT
{
int x, y;
} P[100001],Y[100001],B[100001],Z[100001];
inline double distanta(PUNCT a, PUNCT b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cmp(PUNCT a, PUNCT b)
{
return (a.x<b.x);
}
int cmpy(PUNCT a, PUNCT b)
{
return (a.y<b.y);
}
double divImp(int st, int dr)
{
if(dr-st==1)
{
if(B[st].y>B[dr].y)
{
swap(B[st].x,B[dr].x);
swap(B[st].y,B[dr].y);
}
return distanta(P[st],P[dr]);
}
if(dr-st==2)
{
sort(B+st,B+dr+1,cmpy);
return min(distanta(P[st],P[st+1]),min(distanta(P[st+1],P[dr]),distanta(P[st],P[dr])));
}
int mij=(st+dr)/2,i,j,k;
double d=min(divImp(st,mij),divImp(mij+1,dr));
for(i=st, j=mij+1, k=st; i<=mij && j<=dr; )
if(B[i].y<B[j].y)
Y[k++]=B[i++];
else
Y[k++]=B[j++];
while(i<=mij)
Y[k++]=B[i++];
while(j<=dr)
Y[k++]=B[j++];
for(int ind=st; ind<=dr; ind++)
B[ind]=Y[ind];
int nr=0;
for(int ind=st,i=1; ind<=dr; ind++)
if(abs(P[mij].x-B[ind].x)<=d)
{
Z[i].x=B[ind].x;
Z[i++].y=B[ind].y;
nr++;
}
for(i=1; i<=nr-7; i++)
for(int j=i; j<=nr && j<=i+7; j++)
d=min(distanta(Z[i],Z[j]),d);
return d;
}
int main()
{
fi>>n;
for(int i=1; i<=n; i++)
fi>>P[i].x>>P[i].y;
sort(P+1,P+n+1,cmp);
for(int i=1; i<=n; i++)
{
B[i].x=P[i].x;
B[i].y=P[i].y;
}
fo<<fixed<<setprecision(6)<<divImp(1,n);
fi.close();
fo.close();
return 0;
}