Cod sursa(job #3208604)

Utilizator Alex_BerbescuBerbescu Alexandru Alex_Berbescu Data 28 februarie 2024 23:59:22
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
// cele mai apropiate puncte in plan
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int> >v;
set<pair<int, int> >hasu;
double mini = 1e9, a, b;
int n;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int32_t main(int argc, char * argv[])
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
    {
        fin >> a >> b;
        v.push_back({a, b});
    }
    sort(v.begin(), v.end());
    hasu.insert({v[0].first, v[0].second});
    for(int i = 1; i < n; ++i)
    {
        auto l = hasu.lower_bound({v[i].first - mini, v[i].second - mini});
        auto r = hasu.upper_bound({v[i].first, v[i].second + mini});
        if(l == hasu.end())
        {
            continue;
        }
        for(auto p = l; p != r; p++)
        {
            pair<int, int>val = *p;
            double dist = (double)((double)v[i].first - val.first) * (double)((double)v[i].first - val.first) + (double)((double)v[i].second - val.second) * (double)((double)v[i].second - val.second);
            if(mini > dist)
            {
                mini = dist;
            }

        }
        hasu.insert({v[i].first, v[i].second});
    }
    fout << fixed << setprecision(6) << sqrt((double)mini);
    return 0;
}