Cod sursa(job #2249667)

Utilizator AlexutAlex Calinescu Alexut Data 30 septembrie 2018 09:58:32
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define punct pair<double,double>
#define fi first
#define se second
using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");
const int N=100010;
int n,i,k;
punct v[N],p;
set<punct>M;
double x,y,d,oo=2000000001.0;
inline double dist(punct a,punct b)
{
    return sqrt((a.fi-b.fi)*(a.fi-b.fi)+(a.se-b.se)*(a.se-b.se));
}

int main()
{
    f>>n;
    for(int i=0;i<n;i++)
    {
        f>>x>>y;
        v[i]=make_pair(x,y);
    }
    sort(v,v+n);
    M.insert(make_pair(v[0].se,v[0].fi));
    d=2000000001.0*sqrt(2.0);
    for(i=1;i<n;i++)
    {
        p=make_pair(v[i].se,v[i].fi);
        while(v[i].fi-v[k].fi>=d)
        {
            M.erase(make_pair(v[k].se,v[k].fi));
            k++;
        }
        set<punct>::iterator it=M.lower_bound(make_pair(p.fi-d-1.0,-oo));
        for(;it!=M.end()&&it->fi-p.fi<=d;it++)
            d=min(d,dist(*it,p));
        M.insert(p);

    }
    g<<fixed<<setprecision(10)<<d;
    return 0;
}