Pagini recente » Cod sursa (job #2814318) | Cod sursa (job #1527976)
#include<fstream>
#include<algorithm>
#define x first
#define y second
#define Point pair<double,double>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
const int Nmax = 100001;
Point v[Nmax],ax[Nmax],q[20];
int N,K,R;
double dist(Point A,Point B){return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y) );}
struct cmp{inline bool operator ()(const Point &A,const Point &B)const{return A.y<B.y;}};
double cmap(int st,int dr){
if(dr-st <= 2){
double sol=1e100;
for(int i=st;i<=dr;i++)
for(int j=i+1;j<=dr;j++) sol=min(sol,dist(v[i],v[j]));
sort(v+st,v+dr+1,cmp());
return sol;
}
else{
int mij=(st+dr)/2;
double MIJ=v[mij].x;
double s1=cmap(st,mij);
double s2=cmap(mij+1,dr);
double ss=min(s1,s2),S=ss;
int i=st,j=mij+1;
K=0;
while(i<=mij && j<=dr){
if(v[i].y<v[j].y) ax[++K]=v[i++];
else ax[++K]=v[j++];
}
while(i<=mij)ax[++K]=v[i++];
while(j<=dr)ax[++K]=v[j++];
R=0;
for(int i=st;i<=dr;i++){
v[i]=ax[i-st+1];
if(abs(v[i].x-MIJ)<=ss){
for(int j=0;j<min(R,12);j++) S=min(S,dist(v[i],q[j]));
q[R%12]=v[i];
R++;
}
}
return S;
}
}
int main(){
in>>N;
for(int i=1;i<=N;i++) in>>v[i].x>>v[i].y;
sort(v+1,v+N+1);
out.precision(8);
out<<fixed<<cmap(1,N)<<'\n';
return 0;
}