Cod sursa(job #1414135)

Utilizator ZenusTudor Costin Razvan Zenus Data 2 aprilie 2015 13:20:04
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <climits>
#include <set>
#include <iomanip>
#include <cmath>
#include <algorithm>

using namespace std;

#define NMAX 100007
#define SQR(x) ((x)*(x))
#define point pair < int , int >
#define x first
#define y second

ifstream f("cmap.in");
ofstream g("cmap.out");

point p[NMAX];
int N;

void read()
{
    f >> N;

    for (int i=1;i<=N;++i)
    f >> p[i].x >> p[i].y;

    sort(p+1,p+N+1);
}

void solve()
{
    int i=1 , j=1 , bst;
    double sol = INT_MAX - 2;
    set < point > atMaxBst;
    set < point > :: iterator it;

    for (;j<=N;++j)
    {
        bst = (int)sol + 1;

        while (i < j && bst < p[j].x - p[i].x)
        {
            atMaxBst.erase({p[i].y,p[i].x});
            i += 1;
        }

        it = atMaxBst.lower_bound( {p[j].y - bst , 0} );

        for (;it != atMaxBst.end() ; ++it)
        {
            if ( (*it).x - p[j].y > bst) break;

            double c = sqrt( 0.0 + SQR( (*it).x - p[j].y ) + SQR( (*it).y - p[j].x) );
            sol = min(sol , c);
        }

        atMaxBst.insert({p[j].y,p[j].x});
    }

    g << fixed << setprecision(7) << sol << '\n';
}

int main()
{

read();
solve();

return 0;
}