Cod sursa(job #2958895)

Utilizator OvidRata Ovidiu Ovid Data 28 decembrie 2022 22:23:18
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.47 kb
#include<bits/stdc++.h>
using namespace std;

string numeFisier="cmap";
ifstream fin(numeFisier+".in"); ofstream fout(numeFisier+".out");
#define cin fin
#define cout fout

#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
#define pdd pair<double,double>

int t, n, m, k, x[100010], y[100010];
pair<int, int> pr[100010];


double dist(pdd p1, pdd p2){
    return (p1.ft-p2.ft)*(p1.ft-p2.ft)+(p1.sc-p2.sc)*(p1.sc-p2.sc);
}
pdd ind_to_pt(int i){
    return mp(x[i], y[i]);
}

pair<double, pair<int, int>> dc(vector<pair<double, int>> &vec){

    if(vec.size()<=3){
        double dist1 = dist(ind_to_pt(vec[0].sc), ind_to_pt(vec[1].sc));
        if(vec.size()<=2){
            return mp(dist1, mp(vec[0].sc, vec[1].sc));
        }
        double dist2=dist(ind_to_pt(vec[1].sc), ind_to_pt(vec[2].sc) );
        double dist3=dist(ind_to_pt(vec[2].sc), ind_to_pt(vec[0].sc) );
        if(dist1<=dist2 && dist1<=dist3){
            return mp(dist1, mp(vec[0].sc, vec[1].sc));
        }
        if(dist2<=dist3){
            return mp(dist2, mp(vec[1].sc, vec[2].sc));
        }
        return mp(dist3, mp(vec[2].sc, vec[0].sc));
    }

    int mid = (vec.size()/2);
    vector<pair<double, int>> vec1={}, vec2={};
    for(int i=0; i<mid; i++){
        vec1.pb(vec[i]);
    }
    for(int i=mid; i<vec.size(); i++){
        vec2.pb(vec[i]);
    }
    auto res1=dc(vec1), res2=dc(vec2);
    //cout<<fixed<<setprecision(12)<<res1.ft<<" "<<res1.sc.ft<<" "<<res1.sc.sc<<"\n";
    //cout<<fixed<<setprecision(12)<<res2.ft<<" "<<res2.sc.ft<<" "<<res2.sc.sc<<"\n";
    auto res = min(res1, res2);

    vector<pair<double, int>> vv1={}, vv2={};

    for(int i=0; i<vec1.size(); i++){
        if( vec1[i].ft>=(vec1.back().ft-res.ft) ){vv1.pb(mp(y[vec1[i].sc], vec1[i].sc));}
    }
    for(int i=0; i<vec2.size(); i++){
        if(vec2[i].ft<=(vec2[0].ft+res.ft))vv2.pb(mp(y[vec2[i].sc], vec2[i].sc));
    }
    vector<pair<double, int>> vv3={};
    for(int i=0, j=0; i<vv1.size() || j<vv2.size();){
        if(i==vv1.size()){
            vv3.pb(vv2[j]);
            j++;
            continue;
        }
        if(j==vv2.size()){
            vv3.pb(vv1[i]);
            i++;
            continue;
        }
        if(vv1[i]<vv2[j]){
            vv3.pb(vv1[i]);
            i++;
            continue;
        }
        else{
            vv3.pb(vv2[j]);
            j++;
            continue;
        }
    };

    for(int i=0; i<vv3.size(); i++){
        for(int j=i-1; j>=max(0ll, i-8); j--){
            res=min(res, mp( dist(ind_to_pt( vv3[i].sc ), ind_to_pt(vv3[j].sc)),
                             mp( vv3[i].sc,vv3[j].sc  )
                             ) );
        }
    }

    vec=vv3;
    return res;
}



int32_t main(){
    INIT
    cin>>n;
    //cout<<"WHAT?1213214";
    for(int i=1; i<=n; i++){
        cin>>x[i]>>y[i];
    }

    for(int i=1; i<=n; i++){
        pr[i]=mp(x[i], i);
    }
    sort(pr+1, pr+1+n);
    vector<pair<double, int>> vec={};
    for(int i=1; i<=n; i++){
        vec.pb(pr[i]);
    }
    //vec.erase(unique(vec.begin(), vec.end()), vec.end());
    auto res = dc(vec);
    if(res.sc.ft>res.sc.sc){
        swap(res.sc.ft, res.sc.sc);
    }
    //cout<<res.sc.ft-1<<" "<<res.sc.sc-1<<" ";
    cout<<fixed<<setprecision(6)<<sqrt(res.ft);
    return 0;
}