Pagini recente » Cod sursa (job #1809939) | Cod sursa (job #2325054) | Cod sursa (job #2197183) | Cod sursa (job #1630514) | Cod sursa (job #1206642)
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
ifstream f("cmap.in");
ofstream o("cmap.out");
struct dat{
int x,y;
} v[100000];
int n, aux[1000000],y[10000000];
bool funct(dat i,dat j){
return i.x>j.x;
}
bool funct1(int i,int j){
return v[i].y>v[j].y;
}
long long int lung(dat p,dat q){
return 1LL*(p.x-q.x)*(p.x-q.x)+1LL*(p.y-q.y)*(p.y-q.y);
}
long long int devide(int l,int r){
if(l+1==r)return lung(v[y[l]],v[y[r]]);
if(l==r)return (1LL*1<<62);
int m=(r+l)/2;
long long int d = min(devide(m+1,r),devide(1,m));
sort(y+l,y+r+1,funct1);
int k=0;
for(int i=l;i<=r;i++)
if(abs(v[m].x-v[y[i]].x)<=d)aux[++k]=y[i];
for(int i=1;i<=k-1;i++)
for(int j=i+1;j<=k && j<=i+7;j++)
d=min(d,lung(v[aux[i]],v[aux[j]]));
return d;
}
int main(){
f>>n;
for(int i=1;i<=n;i++){
f>>v[i].x>>v[i].y;
y[i]=i;
}
sort(v+1,v+1+n,funct);
o<<setprecision(6);
o<<fixed;
o<<sqrt(devide(1,n));
}