Cod sursa(job #3225291)

Utilizator gBneFlavius Andronic gBne Data 17 aprilie 2024 11:52:39
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 100000;
pair<int, int> v[NMax + 10];
pair<int, int> tmp[NMax + 10];

int N;

long long distanta(int x, int y){
    int x2 = v[y].first, x1 = v[x].first;
    int y2 = v[y].second, y1 = v[x].second;
    return (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1);
}

long long solve(int st, int dr){
    if(st == dr){
        return 0;
    }
    else{
        int mij = (st + dr) / 2;
        long long s1 = solve(st, mij);
        long long s2 = solve(mij + 1, dr);
        if(s1 == 0){
            s1 = distanta(st, st + 1);
        }
        if(s2 == 0){
            s2 = distanta(dr - 1, dr);
        }
        long long d = min(s1, s2);
        int k = st, i = st, j = mij + 1;
        while(i <= mij && j <= dr){
            if(v[i].second < v[j].second){
                tmp[k ++] = v[i ++];
            }
            else{
                tmp[k ++] = v[j ++];
            }
        }
        while(i <= mij){
            tmp[k ++] = v[i ++];
        }
        while(j <= dr){
            tmp[k ++] = v[j ++];
        }
        for(int i=st; i<=dr; ++i){
            v[i] = tmp[i];
        }

        i = mij - 1;
        vector<int> p;
        while(distanta(mij, i) <= d && i > 0){
           p.push_back(i);
           -- i;
        }
        i = mij + 1;
        while(distanta(mij, i) <= d && i <= N){
            p.push_back(i);
            ++ i;
        }
        for(int i=0; i<p.size(); ++i){
            for(int j=i+1; j<p.size(); ++j){
                d = min(d, distanta(p[i], p[j]));
            }
        }
        return d;
    }
}

int main()
{
    fin >> N;
    for(int i=1; i<=N; ++i){
        fin >> v[i].first >> v[i].second;
    }
    sort(v + 1, v + N + 1);
    fout << setprecision(20) << sqrt(solve(1, N)) << '\n';
    return 0;
}