Pagini recente » Cod sursa (job #2340308) | Cod sursa (job #937408) | Cod sursa (job #2203685) | Cod sursa (job #1331585) | Cod sursa (job #2867904)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct pct
{
int x,y;
} v[100005];
int n;
double minim=1000000000;
int ver[100005];
bool comp(pct a, pct b)
{
if(a.x!=b.x)return a.x<b.x;
else return a.y<b.y;
}
double distanta(int i, int j)
{
pct a=v[i];
pct b=v[j];
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool compy(int i, int j)
{
return v[i].y<=v[j].y;
}
double comb(int s, int d)
{
int nr=0;
int mij=(s+d)/2;
for(int i=s; i<=d; i++)
{
if(abs(v[mij].x-v[i].x)<minim&&abs(v[mij].y-v[i].y)<minim)
{
ver[++nr]=i;
}
}
sort(ver+1,ver+nr+1,compy);
for(int i=1; i<=nr; i++)
{
for(int j=i+1; j<=nr&&j<=i+7; j++)
{
minim=min(minim,distanta(ver[i],ver[j]));
}
}
}
double divide(int s, int d)
{
if(d-s>1)
{
if(d-s<=2)
{
minim=distanta(s,s+1);
if(d-s==2)
{
minim=min(minim,min(distanta(s+1,s+2),distanta(s,s+2)));
}
return minim;
}
int mij=(s+d)/2;
minim=min(divide(s,mij),divide(mij+1,d));
minim=min(minim,comb(s,d));
}
return minim;
}
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,comp);
divide(1,n);
fout<<setprecision(6)<<fixed<<minim;
return 0;
}