Pagini recente » Cod sursa (job #2731813) | Cod sursa (job #1142407) | Cod sursa (job #475225) | Cod sursa (job #1157605) | Cod sursa (job #1862965)
#include<algorithm>
#include<iostream>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#define inf 5999999999
#define y second
#define x first
using namespace std;
fstream fin("cmap.in",ios::in),fout("cmap.out",ios::out);
vector<pair<int,int> > v,aux;
int n;
void citire()
{
int i,a,b;
fin>>n;
for(i=0;i<n;i++)
{
fin>>a>>b;
v.push_back({a,b});
}
}
double dist(int ax,int ay,int bx,int by)
{
long long c,d;
c=(ax-bx);c=c*c;
d=(ay-by);d=d*d;
c=c+d;
return sqrt(c);
}
double solv(int st,int dr)
{
int m=(st+dr)/2,i,j,d;
double minim=inf;
if(dr-st<=3)
{
for(i=st;i<=dr;i++)
{
for(j=i+1;j<=dr;j++)
{
minim=min(minim,dist(v[i].x,v[i].y,v[j].x,v[j].y));
}
}
}
else
{
minim=min(solv(st,m),solv(m+1,dr));
aux.clear();
d=v[m].x;
for(i=st;i<=dr;i++)
{
if(dist(v[i].x,v[i].y,d,v[i].y)<=minim)
{
aux.push_back(v[i]);
}
}
for(i=0;i<aux.size();i++)
{
for(j=i+1;j<aux.size() && j<i+8;j++)
{
minim=min(minim,dist(aux[i].x,aux[i].y,aux[j].x,aux[j].y));
}
}
}
return minim;
}
int main()
{
double dis;
citire();
sort(v.begin(),v.end());
dis=solv(0,n-1);
fout<<fixed<<setprecision(7)<<dis;
}