Cod sursa(job #2489184)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 7 noiembrie 2019 23:56:25
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define nmax 100005
#define inf ((1<<30) - 1)
using namespace std;

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

int n;
struct point
{
    int x, y;
    bool operator < (const point &ot) const
    {
        if (x == ot.x)
            return y < ot.y;
        return x < ot.x;
    }
} v[nmax];
set < point > s;

double dist(point a, point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main()
{
    f >> n;
    for (int i = 0; i < n; ++ i)
        f >> v[i].x >> v[i].y;

    sort(v, v + n);

    double dist_min = dist(v[0], v[1]);
    int k = 0;

    for (int i = 0; i < n; ++ i) {

        while (k < i && double(v[i].x - v[k].x) >= dist_min)
            s.erase(s.find(point{v[k].y, v[k++].x}));


        int dist_int = int(dist_min);
        auto it1 = s.lower_bound(point{v[i].y - dist_int ,-inf});
        auto it2 = s.upper_bound(point{v[i].y + dist_int, inf});


        if (it2 != s.begin() && it1 != s.end())
            for (auto it3 = it1; it3 != it2; ++it3)
                dist_min = min(dist_min , dist(v[i], point{it3->y, it3->x}));

        s.insert(point{v[i].y, v[i].x});
    }

    g << setprecision(10) << fixed << dist_min;

    return 0;
}