Cod sursa(job #2191304)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 2 aprilie 2018 14:45:30
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 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];
int n,i;
long double dist(int x1,int Y1,int x2,int y2){
    return sqrt((x1-x2)*(x1-x2)+(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;
    long double sol=min(cmap(st,mij),cmap(mij+1,dr));
    sort(v+st,v+dr+1);
    for(int i=st;i<=dr;i++)
        for(int j=i+1;j<=min(i+8,dr);j++)
            sol=min(sol,dist(v[i].x,v[i].y,v[j].x,v[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;
}