Cod sursa(job #2969125)

Utilizator AswVwsACamburu Luca AswVwsA Data 22 ianuarie 2023 16:38:21
Problema Cele mai apropiate puncte din plan Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <set>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#define int long long
using namespace std;

const int NMAX = 1e5;
struct pct
{
    int x, y;
}v[NMAX + 1];

bool operator <(pct a, pct b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

set <pct> points;

long long dist(pct a, pct b)
{
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}
signed main()
{
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");
    int n, i;
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1);
    long long mn = INT_MAX / 2;
    for (i = 1; i <= n; i++)
    {
        if (!points.empty())
        {
            //cout << v[i].x << ' ' << v[i].y << "\n";
            auto it1 = points.upper_bound({v[i].x + mn, INT_MAX});
            auto it2 = points.lower_bound({v[i].x - mn, 0});
            auto it = next(it2);
            while (it != points.end() and it != it1)
            {
                if (abs(it->y - v[i].y) > mn)
                {
                    auto aux = next(it);
                    points.erase(it);
                    it = aux;
                }
                else
                {
                    long long d = dist(*it, v[i]);
                    if (d < mn)
                    {
                        mn = d;
                    }
                    it++;
                }
            }
        }
        points.insert(v[i]);
    }
    cout << fixed << setprecision(6) << sqrt(mn);
}