Pagini recente » Cod sursa (job #166928) | Cod sursa (job #3031427) | Cod sursa (job #1621827) | Cod sursa (job #1274106) | Cod sursa (job #1110278)
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#define INF 2000000000
using namespace std;
int n,nry;
struct punct
{
double x,y;
}v[100001],py[100001];
ifstream fin("cmap.in");
ofstream fout("cmap.out");
void citire()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
}
int cmp(punct a,punct b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
inline double dist(punct a,punct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)*1.0);
}
int cmp2(punct a,punct b)
{
return a.y<b.y;
}
double imparte(int p,int u)
{
double dmin=INF*1.0;
int mij;
if(u-p+1<=3)
{
for(int i=p;i<u;i++)
for(int j=i+1;j<=u;j++)
dmin=min(dmin,dist(v[i],v[j]));
return dmin;
}
mij=(p+u)/2;
dmin=min(imparte(p,mij),imparte(mij+1,u));
nry=0;
for(int i=mij+1;i<=u && v[i].y-v[mij].y<=dmin+1.0;i++)
{
py[++nry].x=v[i].x;
py[nry].y=v[i].y;
}
for(int i=mij;i>=p && v[mij].y-v[i].y<=dmin+1.0;i--)
{
py[++nry].x=v[i].x;
py[nry].y=v[i].y;
}
sort(py+1,py+nry+1,cmp2);
for(int i=1;i<=nry;i++)
{
for(int j=i+1;j<=nry && j<=i+8;j++)
{
dmin=min(dmin,dist(py[i],py[j]));
}
}
return dmin;
}
int main()
{
citire();
sort(v+1,v+n+1,cmp);
fout<<setprecision(6)<<fixed<<imparte(1,n);
return 0;
}