Pagini recente » Cod sursa (job #1981382) | Cod sursa (job #2207033) | Cod sursa (job #1090692) | Cod sursa (job #1248095) | Cod sursa (job #781448)
Cod sursa(job #781448)
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#define inf 1000000000
using namespace std;
typedef struct w{int x,y;}point;
point a[100005],aux[50005];
bool cmp(point a,point b){if (a.x==b.x) return(a.y<b.y); else return(a.x<b.x); }
bool cmp1(point a,point b){if (a.y==b.y) return(a.x<b.x); else return(a.y<b.y); }
long long abs(long long w){if (w>0) return(w); else return(-w); }
long long dist(point a, point b){ return((long long)(a.x-b.x)*(a.x-b.x)+(long long)(a.y-b.y)*(a.y-b.y)); }
long long min(long long a,long long b){if (a<b) return(a); else return(b); }
long long solution(int l, int r){
if (l>=r-1) return(inf);
else if (l-r==2) return(min(dist(a[l],a[l+1]),min(dist(a[l],a[l+2]),dist(a[l+1],a[l+2]))));
int mid=(l+r)/2;
long long sl=solution(l,mid);
long long sr=solution(mid+1,r);
long long s=min(sl,sr);
int nr=0,i,j;
for (i=l; i<=r; ++i)
if (abs(a[i].x-mid)<=s) {++nr; aux[nr]=a[i]; }
sort(aux+1,aux+nr+1,cmp1);
for (i=1; i<nr; ++i){
int lim;
if (i+8<=nr) lim=i+8; else lim=nr;
for (j=i+1; j<=lim; ++j) s=min(s,dist(aux[i],aux[j]));
}
return(s);
}
int main(void){
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int i,n; fin>>n;
for (i=1; i<=n; ++i) fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
fout<<fixed<<setprecision(6)<<sqrt(solution(1,n));
return(0);
}