Cod sursa(job #1198862)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 17 iunie 2014 14:42:32
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>

using namespace std;

const int NMAX = 100000+5;

struct Point
{
    int x,y;
    Point()
    {
        x=0;
        y=0;
    }
    Point(int _x,int _y)
    {
        x=_x;
        y=_y;
    }
};

inline bool sortByX(const Point &A,const Point &B)
{
    if(A.x==B.x) return A.y<B.y;
    return A.x<B.x;
}

struct sortByY
{
    inline bool operator()(const Point &A,const Point &B)
    {
        return A.y<B.y;
    }
};

inline double dist(const Point &A,const Point &B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

void Read(),Solve(),Print();

int N;
Point P[NMAX];
set<Point,sortByY> S;
double bestDist;

int main()
{
    Read();
    Solve();
    Print();

    return 0;
}

void Read()
{
    int i;

    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);

    scanf("%d",&N);

    for(i=1; i<=N; i++)
        scanf("%d%d",&P[i].x,&P[i].y);
}

void Solve()
{
    int i,j;
    Point R;
    double best;
    set<Point,sortByY>::iterator it;

    sort(P+1,P+N+1,sortByX);

    bestDist=dist(P[1],P[2]);
    S.insert(P[1]);
    S.insert(P[2]);

    for(i=3,j=1; i<=N; i++)
    {
        while(P[i].x-P[j].x>bestDist+1 && j<i)
        {
            S.erase(P[j]);
            j++;
        }

        R=Point(P[i].x,P[i].y-bestDist-1);
        best=bestDist;

        for(it=S.lower_bound(R); (it!=S.end()) && (it->y-P[i].y<=bestDist); it++)
            best=min(best,dist(*it,P[i]));

        bestDist=min(best,bestDist);

        S.insert(P[i]);
    }
}

void Print()
{
    printf("%.7lf\n",bestDist);
}