Cod sursa(job #1714600)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 8 iunie 2016 20:05:32
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
# include <fstream>
# include <algorithm>
# include <cmath>
# include <iomanip>
# define DIM 100010
# define INF 2000000000000000000LL
# define f first
# define s second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
pair <int,int> v[DIM],sol[DIM],vec[DIM];
long long m,x,a,b,c,d;
int n,i,j,r;
void inter(int st,int dr){
    int mij=(st+dr)/2,k=0,i=st,j=mij+1;
    while(i<=mij&&j<=dr)
        if(v[i].s<v[j].s)
            sol[++k]=v[i++];
        else
            sol[++k]=v[j++];
    for(;i<=mij;i++)
        sol[++k]=v[i];
    for(;j<=dr;j++)
        sol[++k]=v[j];
}
long long cmap(int st,int dr){
    if(st==dr)
        return INF;
    else{
        int mij=(st+dr)/2;
        int val=v[mij].f;
        long long m1=cmap(st,mij);
        long long m2=cmap(mij+1,dr);
        m=min(m1,m2);
        inter(st,dr);
        for(i=st;i<=dr;i++)
            v[i]=sol[i-st+1];
        r=0;
        for(i=st;i<=dr;i++){
            if(v[i].f>=val-m||v[i].f<=val+m+1)
                vec[++r]=v[i];
        }
        for(i=1;i<=r;i++){
            for(j=i+1;j<=i+8&&j<=r;j++){
                a=v[i].f;
                b=v[j].f;
                c=v[i].s;
                d=v[j].s;
                x=(a-b)*(a-b)+(c-d)*(c-d);
                m=min(m,x);
            }
        }
        return m;
    }
}
int main () {
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i].f>>v[i].s;
    sort(v+1,v+n+1);
    fout<<setprecision(6)<<fixed<<sqrt(cmap(1,n))<<"\n";
    return 0;
}