Cod sursa(job #2958922)

Utilizator OvidRata Ovidiu Ovid Data 28 decembrie 2022 23:17:44
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.35 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<int,int>
#define double int

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){
    vector<pii> vv3={};
    pair<int, pii> res={1e18, {1e18, 1e18}};
    if(vec.size()>3){
        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]);
        }
        double end1=vec1.back().ft;
        double end2=vec2[0].ft;
        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";
        res = min(res1, res2);

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

        for(int i=0; i<vec1.size(); i++){
            if( x[vec1[i].sc]>=(end1-res.ft) ){vv1.pb(mp(y[vec1[i].sc], vec1[i].sc));}
        }
        for(int i=0; i<vec2.size(); i++){
            if(x[vec2[i].sc]<=(end2+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;
            }
        };
    }
    else{
       for(int i=0; i<vec.size(); i++){
           vv3.pb(mp(y[vec[i].sc], vec[i].sc));
       }
       sort(vv3.begin(), vv3.end());
    }


    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;
}