Cod sursa(job #3244062)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 23 septembrie 2024 11:33:23
Problema Cele mai apropiate puncte din plan Scor 55
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define int long long

using namespace std;

const string TASK("cmap");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout

const int N = 1e5 + 9, Inf = 0x3f3f3f3f;

struct point
{
    int x, y;
};

struct cmp
{
    bool operator () (point const& a, point const& b) const noexcept
    {
        return a.y == b.y ? a.x < b.x : a.y < b.y;
    }
};

int dist(point const& a, point const& b)
{
    return (a.x - b.x) * (a.x - b.x) +
            (a.y - b.y) * (a.y - b.y);
}


int n;
point a[N];

signed main()
{
    cin >> n;
    FOR(i, 1, n)cin >> a[i].x >> a[i].y;

    sort(a + 1, a + n + 1, [](point a, point b)
         {
             return a.x < b.x;
         });

    set<point, cmp> st;

    int d = Inf, p = 1;
    FOR(i, 1, n)
    {
        while(p <= n && a[p].x < a[i].x - d)
        {
            st.erase(a[p]);
            p ++;
        }

        auto it1 = st.lower_bound({a[i].x - d, a[i].y - d});
        auto it2 = st.upper_bound({a[i].x - d, a[i].y + d});
        for(; it1 != it2; ++it1)
            d = min(d, dist(a[i], *it1));

        st.insert(a[i]);
    }

    cout << fixed << setprecision(12);
    cout << sqrt(d);
    return 0;
}