Cod sursa(job #1198860)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 17 iunie 2014 14:37:13
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 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;
    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);

        for(it=S.lower_bound(R); it!=S.end(); it++)
            bestDist=min(bestDist,dist(*it,P[i]));

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

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