Cod sursa(job #2971912)

Utilizator LuxinMatMatasaru Luxin Gabriel LuxinMat Data 28 ianuarie 2023 12:30:32
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<algorithm>
#include<set>
#include<cmath>
#include<deque>
#include<iomanip>
#include<iostream>
using namespace std;

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

struct ura
{
    int x, y;

    bool operator<(const ura& rhs) const
    {
        if(y == rhs.y)
            return x < rhs.x;
        return y < rhs.y;
    }
} v[100001];

set<ura> s;
deque<set<ura>::iterator> d;

bool cmp(ura a, ura b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

double dist(ura a,  ura b)
{
    uint64_t dist2 = (a.x-b.x) * (a.x-b.x) + (a.y-b.y)*(a.y-b.y);
    return sqrt(dist2);
}

int main()
{
    int n;
    in>>n;

    for(int i=1; i<=n; i++)
    {
        int x, y;
        in>>x>>y;
        v[i] = {x, y};
    }

    sort(v+1, v+n+1, cmp);

    double dmin = 1e9;

    for(int i=1; i<=n; i++)
    {
        auto it = s.lower_bound({0, v[i].y-dmin-1});


        while((*it).y <= v[i].y + dmin + 1 && it != s.end())
        {
            if((*it).x < v[i].x - dmin - 1)
                d.push_back(it);
            else
                dmin = min(dmin, dist(*it, v[i]));

            ++it;
        }

        for(auto it1 : d)
        {
            s.erase(it1);
            d.pop_front();
        }

        s.insert(v[i]);
    }

    out<<fixed<<setprecision(6)<<dmin;
    return 0;
}