Cod sursa(job #2617504)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 21 mai 2020 20:58:44
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

ifstream f ("cmap.in");
ofstream g ("cmap.out");

typedef pair <int, int> PI;

constexpr int NMAX = 1e5 + 5;

int N;
PI a[NMAX];

set <PI> R;

void Read ()
{
    f >> N;

    for (int i = 1; i <= N; ++i)
        f >> a[i].x >> a[i].y;

    sort(a+1, a+N+1);
}

double Distance (PI a, PI b)
{
    return sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}

void Solve ()
{
    double sol = 2e9;
    int ind_Left = 1;

    for (int i = 1; i <= N; ++i)
    {
        while (!R.empty() && a[i].x - a[ind_Left].x >= sol)
        {
            R.erase({a[ind_Left].y, a[ind_Left].x});

            ++ind_Left;
        }

        int y_Down = a[i].y - (int)(sol);
        int y_Up = a[i].y + (int)(sol);

        set <PI> :: iterator d = R.lower_bound({y_Down, 1e9});
        set <PI> :: iterator u = R.lower_bound({y_Up, 1e9});

        for (set <PI> :: iterator it = d; it != u; ++it)
        {
            PI nr = *it;

            swap(nr.x, nr.y);

            double ans = Distance(nr, a[i]);

            sol = min(sol, ans);
        }

        R.insert({a[i].y, a[i].x});
    }

    g << setprecision(6) << fixed;
    g << sol << '\n';
}

int main()
{
    Read();

    Solve();
    return 0;
}