Pagini recente » Cod sursa (job #2483242) | Cod sursa (job #539442) | Cod sursa (job #2934103) | Cod sursa (job #21227) | Cod sursa (job #2969230)
#include <iostream>
#include <algorithm>
#include <math.h>
#define NMAX 100000
#define INF 1000000000
using namespace std;
struct pct{
int x,y;
};
pct v[NMAX];
pct p[NMAX];
int i,n,nr;
bool comp(const pct &a,const pct &b){
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
bool c(const pct &a,const pct &b){
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
double dist(const pct& a, const pct& b) {
return sqrt((double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y));
}
double ver(double d){
int j;
sort(p,p+nr,c);
for(i=0;i<nr-1;i++){
j=i+1;
while(j<nr && p[j].y-p[i].y<d){
d=min(d,dist(p[i],p[j]));
j++;
}
}
return d;
}
double solve(int l,int r){
if(r-l+1<=3){
double mmin=INF;
for(i=l+1;i<=r;i++){
mmin=min(mmin,dist(v[l],v[i]));
}
return mmin;
}else{
double d;
int m=(l+r)/2;
d=min(solve(l,m),solve(m+1,r));
nr=0;
for(;l<=r;l++){
if(abs(v[l].x-v[m].x)<d){
p[nr++]=v[l];
}
}
return min(d,ver(d));
}
}
int main(){
FILE *fin,*fout;
fin=fopen("cmap.in","r");
fout=fopen("cmap.out","w");
fscanf(fin,"%d",&n);
for(i=0;i<n;i++){
fscanf(fin,"%d%d",&v[i].x,&v[i].y);
}
sort(v,v+n,comp);
fprintf(fout,"%.6f",solve(0,n-1));
fclose(fin);
fclose(fout);
return 0;
}