Cod sursa(job #1841938)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 6 ianuarie 2017 12:21:14
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
#define X first
#define Y second
#define punct pair<int,int>


using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
punct p[100010];
set<punct > q;
double dist(punct,punct);
int n,i,j,x,y,D;
double d;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        p[i]={x,y};
    }
    sort(p+1,p+n+1);
    d=dist(p[1],p[2]);
    q.insert({p[1].Y,p[1].X});
    q.insert({p[2].Y,p[2].X});
    j=1;
    for(i=3;i<=n;i++)
    {
        punct P={p[i].Y,p[i].X};
        while((double)(p[i].X-p[j].X)>=d)
        {
            q.erase({p[j].Y,p[j].X});
            j++;
        }
        D=d+1;
        punct Q={P.X-D,-1000000001};
        auto it=upper_bound(q.begin(),q.end(),Q);
        while(it!=q.end()&&it->X-P.X<D)
        {
            d=min(d,dist(P,*it));
            it++;
        }
        q.insert(P);
    }
    g<<fixed<<setprecision(10)<<d;
    return 0;
}
double dist(punct u,punct v)
{
    return 1.0*sqrt((u.X-v.X)*(u.X-v.X)+1.0*(u.Y-v.Y)*(u.Y-v.Y));
}