Cod sursa(job #2213783)

Utilizator unknownpersonBidasca Carina Georgiana unknownperson Data 17 iunie 2018 13:48:51
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 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;
punct v[N],p;
set<punct>M;
punct sim(punct a){return make_pair(a.se,a.fi);}
double x,y,d,oo=2000000001.0;
set<punct>::iterator lo(punct a){return M.lower_bound(make_pair(a.fi-d,-oo));}
double dist(punct a,punct b)
{
    return sqrt((a.fi-b.fi)*(a.fi-b.fi)+(a.se-b.se)*(a.se-b.se));
}
double dy(punct a,punct b)
{
    return a.fi-b.fi;
}
int main()
{
    f>>n;
    for(int i=0;i<n;i++)
    {
        f>>x>>y;
        v[i]=make_pair(x,y);
    }
    sort(v+1,v+n+1);
    M.insert(v[0]);
    d=2000000001.0*sqrt(2.0);
    for(i=1;i<n;i++)
    {
        p=sim(v[i]);
        for(auto it=lo(p);it!=M.end()&&dy(*it,p)<=d;it++)
            d=min(d,dist(*it,p));
        M.insert(p);

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