Cod sursa(job #717604)

Utilizator algotrollNume Fals algotroll Data 20 martie 2012 08:06:15
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<cstdio>
#include<cmath>
#include<set>
#include<vector>
#include<algorithm>
#define INF 100000000000

struct point
{
    int x,y;
};
struct lower_y
{
    bool operator() (point A, point B)
    {
        return A.y<B.y;
    }
};

double dist(point A, point B)
{
    return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

bool lower_x (point A, point B)
{
    return A.x<B.x;
}

int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    int nP; scanf("%d",&nP);
    std::vector<point> sweep;
    for (int i=1;i<=nP;i++)
    {
        point tmp;
        scanf("%d %d",&tmp.x,&tmp.y);
        sweep.push_back(tmp);
    }
    std::sort(sweep.begin(),sweep.end(),lower_x);
    //
    float mind=INF;
    std::set<point,lower_y> setEval;
    for (int i=0; i<sweep.size(); i++)
    {
        point cur = sweep.at(i);
        for (std::set<point>::iterator it=setEval.begin();it!=setEval.end();)
            if (dist(cur, *it)<mind)
            {
                mind=dist(cur, *it);
                ++it;
            }
            else
                setEval.erase(it++);
        setEval.insert(cur);
    }
    printf("%.8lf", mind);
    return 0;

}