Cod sursa(job #2989477)

Utilizator DordeDorde Matei Dorde Data 6 martie 2023 18:02:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iomanip>
#define vi vector<int>
#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 , vi &v){
    int S = r - l + 1 , i , j;
    double ans = 1e18;
    if(S <= 3){
        for(i = l ; i <= r ; ++ i){
            for(j = i + 1 ; j <= r ; ++ j){
                ans = min(ans , dist(idx[i] , idx[j]));
            }
            v.push_back(idx[i]);
        }
        sort(v.begin() , v.end() , crt2);
        return ans;
    }
    int m = (l + r) >> 1;
    vi L , R;
    ans = min(solve(l , m , L) , solve(m + 1 , r , R));
    i = j = 0;
    while(i < L.size() && j < R.size()){
        if(Y[L[i]] < Y[R[j]])
            v.push_back(L[i++]);
        else
            v.push_back(R[j++]);
    }
    while(i < L.size()){
        v.push_back(L[i++]);
    }
    while(j < R.size()){
        v.push_back(R[j++]);
    }
    for(i = 0 ; i < S ; ++ i){
        for(j = i + 1 ; j < min(S , i + 8) ; ++ j){
            ans = min(ans , dist(v[i] , v[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);
    vi CV;
    fout << fixed << setprecision(6) << solve(1 , N , CV) << '\n';
    return 0;
}