Cod sursa(job #2642742)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 17 august 2020 01:45:58
Problema Cele mai apropiate puncte din plan Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
vector <pair <int, int> > v;

long long Dist(pair <int, int> a, pair <int, int> b){
    return 1LL * (a.first - b.first) * 1LL * (a.first - b.first) + 1LL * (a.second - b.second) * 1LL * (a.second - b.second);
}

void Merge(int st, int dr){
    vector <pair <int, int> > aux;
    int mid = (st + dr) / 2;
    int p = mid + 1, j = st;
    while (st <= mid && p <= dr){
        if (v[st].second < v[p].second){
            aux.push_back(v[st]);
            ++st;
        }
        else{
            aux.push_back(v[p]);
            ++p;
        }
    }
    while (st <= mid){
        aux.push_back(v[st]);
        ++st;
    }
    while (p <= dr){
        aux.push_back(v[p]);
        ++p;
    }
    for (int i = 0; i < aux.size(); ++i){
        v[j++] = aux[i];
    }
}

int GetMinDist(int st, int dr){
    if (dr - st + 1 <= 3){
        if (dr - st == 2){
            Merge(st + 1, st + 2);
            Merge(st, dr);
            long long dist1 = Dist(v[st], v[st + 1]), dist2 = Dist(v[st], v[st + 2]), dist3 = Dist(v[st + 1], v[st + 2]);
            return min(dist1, min(dist2, dist3));
        }
        else{
            Merge(st, dr);
            return Dist(v[st], v[st + 1]);
        }
    }
    int mid = (st + dr) / 2;
    int midX = v[mid].first;
    long long left = GetMinDist(st, mid);
    long long right = GetMinDist(mid + 1, dr);
    long long minim = min(left, right);
    Merge(st, dr);
    vector <pair <int, int> > aux;
    for (int i = st; i <= dr; ++i){
        if (1LL * abs(midX - v[i].first) * abs(midX - v[i].first) <= minim){
            aux.push_back(v[i]);
        }
    }
    long long minimDist = (1LL << 60);
    for (int i = 0; i < aux.size(); ++i){
        for (int j = i + 1; j - i + 1 <= 8 && j < aux.size(); ++j){
            minimDist = min(minimDist, Dist(aux[i], aux[j]));
        }
    }
    return min(minim, minimDist);
}

int main(){
    fin >> n;
    for (int i = 0; i < n; ++i){
        int x, y;
        fin >> x >> y;
        v.push_back({x, y});
    }
    sort(v.begin(), v.end());
    fout << fixed << setprecision(6) << sqrt(GetMinDist(0, n - 1));
    fin.close();
    fout.close();
    return 0;
}