Cod sursa(job #1166372)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 3 aprilie 2014 15:15:19
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include<cstdio>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const int nmax = 100005;
const double inf = 1000000000000.0;
long long n,i,b,l,r; double best,a;
struct point {long long x,y;} p[nmax];
struct cmps
{
    bool operator () (point a,point b) const
    {
        if(a.y==b.y) return a.x<b.x;
        return a.y<b.y;
    }
};
struct cmp
{
    bool operator () (point a,point b) const
    {
        if(a.x==b.x) return a.y<b.y;
        return a.x<b.x;
    }
};
set<point,cmps> s;
set<point>::iterator it;
double dist(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%lld",&n);
    for(i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y);
    sort(p+1,p+n+1,cmp());
    s.insert(p[1]); best=inf; l=1;
    for(r=2;r<=n;r++)
    {
        b=(long long)(best+1);
        while(l<r && p[l].x+b<p[r].x)
        {
            s.erase(p[l]);
            l++;
        }
        point aux;
        aux.x=p[r].x;
        aux.y=p[r].y-b;
        a=inf;
        it=s.lower_bound(aux);
        while(it!=s.end() && it->y<=p[r].y+b)
        {
            a=min(a,dist(*it,p[r]));
            it++;
        }
        best=min(best,a);
        s.insert(p[r]);
    }
    printf("%lf\n",best);
    return 0;
}