Pagini recente » Cod sursa (job #2486626) | Cod sursa (job #568868) | Cod sursa (job #222572) | Cod sursa (job #1111215) | Cod sursa (job #1024977)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
struct point
{
int x,y;
}p[100000];
int n;
int cmpx(point p1,point p2)
{
return p1.x<p2.x;
}
int cmpy(point p1,point p2)
{
return p1.y<p2.y;
}
double dist(point p1,point p2)
{
double dx=p1.x-p2.x,dy=p1.y-p2.y;
return sqrt(dx*dx+dy*dy);
}
double dmin(point *s,point *e)
{
if(e-s==2)
return dist(*s,*(s+1));
if(e-s==3)
return min(min(dist(*s,*(s+1)),dist(*(s+1),*(s+2))),dist(*s,*(s+2)));
point *m=s+(e-s)/2,*pi;
int drx=m->x;
double dm=min(dmin(s,m),dmin(m,e));
vector<point>area;
vector<point>::iterator iti,itj;
for(pi=m;(pi>=s)&&(drx-(pi->x)<=dm);pi--)
area.push_back(*pi);
for(pi=m+1;(pi<e)&&((pi->x)-drx<=dm);pi++)
area.push_back(*pi);
sort(area.begin(),area.end(),cmpy);
for(iti=area.begin();iti<area.end()-1;iti++)
for(itj=iti+1;(itj<area.end())&&(itj-iti<8);itj++)
dm=min(dm,dist(*iti,*itj));
return dm;
}
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int main()
{
int i;
fin>>n;
for(i=0;i<n;i++)
fin>>p[i].x>>p[i].y;
sort(p,p+n,cmpx);
fout<<setprecision(6)<<fixed<<dmin(p,p+n)<<"\n";
return 0;
}