Cod sursa(job #3293733)

Utilizator mihaigeorgescuGeorgescu Mihai mihaigeorgescu Data 12 aprilie 2025 13:54:44
Problema Cele mai apropiate puncte din plan Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <iomanip>
#include <cmath>
#define int long long
using namespace std;
ifstream fcin("cmap.in");
ofstream fout("cmap.out");
int n;
struct pct
{
    int x,y;
    bool operator<(const pct &a) const
    {
        if(x==a.x)
            return y<a.y;
        return x<a.x;
    }
};
struct cmp
{
    bool operator()(const pct &a, const pct &b) const
    {
        if(a.y==b.y)
            return a.x<b.x;
        return a.y<b.y;
    }
};
pct v[101001];
inline int dist(const pct &a, const pct &b)
{
    return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}
set <pct,cmp> s;
set <pct,cmp>:: iterator it;
signed main()
{
    fcin>>n;
    for(int i=1; i<=n; i++)
        fcin>>v[i].x>>v[i].y;
    sort(v+1, v+n+1);
    int minx=dist(v[1],v[2]), poz=1;
    for(int i=1; i<=n; i++)
    {
        int k=sqrt(minx);
        while(dist(v[i], v[poz])>minx) s.erase(v[poz]), poz++;
        for(it=s.lower_bound({(1<<30), v[i].y-k}); it!=s.end() && it->y<=v[i].y+k; it++)
            minx=min(minx,dist(v[i], *it));
         s.insert(v[i]);
    }
    fout<<fixed<<setprecision(8)<<(long double)sqrt(minx);
    return 0;
}