Cod sursa(job #2191538)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 2 aprilie 2018 23:30:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
# include <fstream>
# include <algorithm>
# include <iomanip>
# include <cmath>
# define DIM 100010
# define INF 1000000000
# define x first
# define y second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
pair<int,int> v[DIM],d[DIM];
int n,i;
long double dist(int x1,int Y1,int x2,int y2){
    return sqrt(1LL*(x1-x2)*(x1-x2)+1LL*(Y1-y2)*(Y1-y2));
}
long double cmap(int st,int dr){
    if(st==dr){
        swap(v[st].x,v[st].y);
        return INF;
    }
    int mij=(st+dr)/2,k=0;
    int X=v[mij].x;
    long double sol=min(cmap(st,mij),cmap(mij+1,dr));
    sort(v+st,v+dr+1);
    for(int i=st;i<=dr;i++)
        if(abs(v[i].y-X)<=sol)
            d[++k]=v[i];
    for(int i=1;i<=k;i++)
        for(int j=i+1;j<=min(i+7,k);j++)
            sol=min(sol,dist(d[i].x,d[i].y,d[j].x,d[j].y));
    return sol;
}
int main () {
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1);
    fout<<setprecision(7)<<fixed<<cmap(1,n);
    return 0;
}