Cod sursa(job #1198859)

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

using namespace std;

const int NMAX = 100000+5;

struct Point
{
    int x,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;
    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(dist(P[j],P[i])>bestDist && j<i)
        {
            S.erase(P[j]);
            j++;
        }
        for(it=S.begin(); it!=S.end(); it++)
            bestDist=min(bestDist,dist(*it,P[i]));
        S.insert(P[i]);
    }
}

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