Cod sursa(job #2989458)

Utilizator DordeDorde Matei Dorde Data 6 martie 2023 17:53:15
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iomanip>
#define sq(x) (1.0*(x)*(x))
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int const D = 1e5 + 3;
int N;
int X[D] , Y[D] , idx[D];
bool crt(int i , int j){
    return X[i] < X[j];
}
bool crt2(int i , int j){
    return Y[i] < Y[j];
}
double dist(int i , int j){
    return sqrt(sq(X[i] - X[j]) + sq(Y[i] - Y[j]));
}
double solve(int l , int r){
    int S = r - l + 1 ;
    double ans = 1e18;
    if(S <= 3){
        for(int i = l ; i <= r ; ++ i){
            for(int j = i + 1 ; j <= r ; ++ j){
                ans = min(ans , dist(idx[i] , idx[j]));
            }
        }
        return ans;
    }
    int m = (l + r) >> 1;
    ans = min(solve(l , m) , solve(m + 1 , r));
    vector<int> p;
    for(int i = l ; i <= r ; ++ i)
        p.push_back(idx[i]);
    sort(p.begin() , p.end());
    for(int i = 0 ; i < S ; ++ i){
        for(int j = i + 1 ; j < min(S , i + 8) ; ++ j){
            ans = min(ans , dist(p[i] , p[j]));
        }
    }
    return ans;
}

int main(){
    fin >> N;
    for(int i = 1 ; i <= N ; ++ i){
        fin >> X[i] >> Y[i];
        idx[i] = i;
    }
    sort(idx + 1 , idx + 1 + N , crt);
    fout << fixed << setprecision(6) << solve(1 , N) << '\n';
    return 0;
}