Cod sursa(job #2978295)

Utilizator DKMKDMatei Filibiu DKMKD Data 13 februarie 2023 17:09:35
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

#define punct pair<int,int>

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
punct v[100010];
set<punct>M;
int i, n, a, b, k;
double d, dist(punct, punct);
int main()
{
    f >> n;
    for (i = 0; i < n; i++)
    {
        f >> a >> b;
        v[i] = make_pair(a, b);
    }
    sort(v, v + n);
    d = 2000000001.0 * sqrt(2.0);
    M.insert(make_pair(v[0].second, v[0].first));
    for (i = 1; i < n; i++)
    {
        for (; (double)(v[i].first - v[k].first) > d; k++)
            M.erase(make_pair(v[k].second, v[k].first));
        punct P = make_pair(v[i].second, v[i].first);
        set<punct>::iterator
            is = M.lower_bound(make_pair((int)(P.first - d - 1), -1000000001));
        for (; is != M.end() && (double)(is->first - P.first) <= d; is++)
            d = min(d, dist(*is, P));
        M.insert(P);
    }
    g << fixed << setprecision(10) << d;
    return 0;
}
double dist(punct A, punct B)
{
    double
        xa = (double)A.first,
        xb = (double)B.first,
        ya = (double)A.second,
        yb = (double)B.second;
    return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
}