Cod sursa(job #3145297)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 14 august 2023 18:06:43
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define pb push_back

ll get_distance(pair<ll,ll> A, pair<ll,ll> B){
    return (A.first-B.first)*(A.first-B.first)+
            (A.second-B.second)*(A.second-B.second);
}

ll find_closest(vector<pair<ll,ll>> &x_sorted, vector<pair<ll,ll>> &y_sorted, int st, int dr){
    if(st>=dr)
        return 4e18;
    if(dr-st==1){
        if(y_sorted[st]>y_sorted[dr])
            swap(y_sorted[st],y_sorted[dr]);
        return get_distance(x_sorted[st],x_sorted[dr]);
    }

    int mid=(st+dr)/2;
    ll dist=min(find_closest(x_sorted,y_sorted,st,mid),find_closest(x_sorted,y_sorted,mid+1,dr));

    sort(y_sorted.begin()+st,y_sorted.begin()+dr+1);

    vector<pair<ll,ll>> points(dr-st+1);
    int len=0;
    for(int i=st;i<=dr;i++){
        if((y_sorted[i].second - x_sorted[mid].first)*(y_sorted[i].second - x_sorted[mid].first)<=dist)
            points[len++]=y_sorted[i];
    }

    for(int i=0;i<len;i++){
        for(int j=i+1;j<len && (points[i].first-points[j].first)*(points[i].first-points[j].first)<=dist;j++){
            dist=min(dist, get_distance(points[i],points[j]));
        }
    }

    return dist;
}

void solve(){
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");

    int N; fin>>N;
    vector<pair<ll,ll>> x_sorted(N);
    vector<pair<ll,ll>> y_sorted(N);
    for(int i=0;i<N;i++)
        fin>>x_sorted[i].first>>x_sorted[i].second;

    sort(x_sorted.begin(), x_sorted.end());
    for(int i=0;i<N;i++)
        y_sorted[i]={x_sorted[i].second, x_sorted[i].first};

    fout<<fixed<<setprecision(10)<<sqrt(find_closest(x_sorted, y_sorted, 0, N-1));
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    solve();
    return 0;
}