Pagini recente » Cod sursa (job #941723) | Cod sursa (job #283818) | Cod sursa (job #974871) | Cod sursa (job #245851) | Cod sursa (job #1091321)
#include <stdio.h>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
//FILE * fin, *fout;
pair <long long, long long> p[100001];
//long long x[100000],y[100000];
int n;
double minim=1e10;
double f(int pst,int pdr)
{
if (pdr-pst <=2)
if (pdr-pst == 1)
{
int i = pst, j = pdr;
return sqrt((p[i].first-p[j].first)*(p[i].first-p[j].first)+
(p[i].second-p[j].second)*(p[i].second-p[j].second));
}
else
{
int i = pst, j = pdr, k = pst+1;
double d1 = sqrt((p[i].first-p[j].first)*(p[i].first-p[j].first)+
(p[i].second-p[j].second)*(p[i].second-p[j].second));
double d2 = sqrt((p[i].first-p[k].first)*(p[i].first-p[k].first)+
(p[i].second-p[k].second)*(p[i].second-p[k].second));
double d3 = sqrt((p[k].first-p[j].first)*(p[k].first-p[j].first)+
(p[k].second-p[j].second)*(p[k].second-p[j].second));
return min(d1,min(d2,d3));
}
else
{
int pmj = (pst+pdr)/2;
double d1 = f(pst,pmj);
double d2 = f(pmj+1,pdr);
double d = min(d1,d2);
vector <pair <long long,long long> > v;
for (int i=pmj+1;i<=n;i++)
if (p[i].first-p[pmj].first < d)
v.push_back(p[i]);
else
break;
for (int i=pmj;i>=1;i--)
if (p[pmj].first-p[i].first < d)
v.push_back(p[i]);
else
break;
sort(v.begin(),v.end());
for (unsigned i=0;i<v.size()-1;i++)
for (unsigned j=i+1;j< min(i+7,v.size());j++)
{
double dd = sqrt((p[i].first-p[j].first)*(p[i].first-p[j].first)+
(p[i].second-p[j].second)*(p[i].second-p[j].second));
if (dd<d)
d = dd;
}
return d;
}
}
int main()
{
//fin = fopen("cmap.in","rt");
//fout = fopen("cmap.out","wt");
fin>>n;
//fscanf(fin,"%d",&n);
for(int i=1;i<=n;i++)
{
fin>>p[i].first>>p[i].second;
//int bufx,bufy;
//fscanf(fin,"%d%d",&bufx,&bufy);
//x[i] = bufx, y[i] = bufy;
}
sort(p+1,p+n+1);
/*
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
long long a=(p[i].first-p[j].first)*(p[i].first-p[j].first)+
(p[i].second-p[j].second)*(p[i].second-p[j].second);
if(sqrt(a)<minim)
minim=sqrt(a);
}
fout.precision(20);
fout<<minim<<endl;
//fprintf(fout,"%fl",minim);
*/
fout.precision(20);
fout << f(1,n);
return 0;
}