Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #304818) | Monitorul de evaluare | Cod sursa (job #1498569)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
const int Nmax = 100001;
struct pnt{
double x,y;
bool operator < (const pnt &t) const {
if(y==t.y) return x<t.x;
return y<t.y;
}
};
pnt v[Nmax],au[Nmax];
int N;
struct cmpx{inline bool operator () (const pnt &A,const pnt &B) const {return A.x < B.x;}};
struct cmpy{inline bool operator () (const pnt &A,const pnt &B) const {return A.y < B.y;}};
double dist(pnt A,pnt B){return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);}
double calc(int st,int dr){
if(dr-st<=2){
double ans=1e20;
for(int i=st;i<=dr;i++) for(int j=i+1;j<=dr;j++) ans=min(ans,dist(v[i],v[j]));
sort(v+st,v+dr+1,cmpy());
return sqrt(ans);
}
else{
int mij=(st+dr)/2;
double s1 = calc(st,mij);
double s2 = calc(mij+1,dr);
double S=min(s1,s2);
double sol=1e20,midp=v[mij].x;
int i=st,j=mij+1,k=0;
while(i<=mij && j<=dr){if(v[i]<v[j]) au[++k]=v[i++];else au[++k]=v[j++];}
while(i<=mij) au[++k]=v[i++];
while(j<=dr) au[++k]=v[j++];
for(i=1;i<=k;i++) v[st+i-1]=au[i];
int stt=1,drr=0;
for(int i=st;i<=dr;i++){
if(abs(v[i].x-midp) <= S){
au[++drr]=v[i];
if(drr-stt > 12) stt++;
for(int j=stt;j<drr;j++){
sol=min(sol,dist(au[j],au[drr]));
}
}
}
return min(sqrt(sol),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,cmpx());
double a = calc(1,N);
out.precision(7);
out<<fixed<<a<<'\n';
return 0;
}