Pagini recente » Cod sursa (job #1359687) | Cod sursa (job #2118244) | Cod sursa (job #2772997) | Cod sursa (job #2606942) | Cod sursa (job #701791)
Cod sursa(job #701791)
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define NMAX 100001
#define INF (1ll<<60)
using namespace std;
pair <int,int> p[NMAX];
int n,m,q[NMAX];
void read()
{
int i;
ifstream f("cmap.in");
f>>n;
for(i=1;i<=n;i++)
f>>p[i].first>>p[i].second;
f.close();
}
inline long long minim(long long a, long long b)
{
if (a<b)
return a;
return b;
}
struct cmp
{
bool operator () (const int &a,const int &b)
{
return p[a].second<p[b].second;
}
};
inline long long distanta(pair <int,int> a, pair <int,int> b)
{
return (long long)(a.first-b.first)*(a.first-b.first)+(long long)(a.second-b.second)*(a.second-b.second);
}
long long calc(int st, int dr)
{
long long dist;
int mij,i,j;
if(dr-st<=2)
{
dist=INF;
for(i=st;i<dr;i++)
for(j=i+1;j<=dr;j++)
dist=minim(dist,distanta(p[i],p[j]));
return dist;
}
mij=(st+dr)/2;
dist=minim(calc(st,mij),calc(mij+1,dr));
m=0;
for(i=st;i<=dr;i++)
if(abs(p[i].second-p[mij].second)<=dist)
q[++m]=i;
sort(q+1,q+m+1,cmp());
for(i=1;i<m;i++)
for(j=i+1;j<=m && j-i<8;j++)
dist=minim(dist,distanta(p[q[i]],p[q[j]]));
return dist;
}
int main()
{
ofstream g("cmap.out");
read();
sort(p+1,p+n+1);
g<<fixed<<setprecision(6)<<sqrt(calc(1,n))<<"\n";
g.close();
return 0;
}