Cod sursa(job #1525531)

Utilizator UMihneaUngureanu Mihnea UMihnea Data 15 noiembrie 2015 10:52:11
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#define punct pair<double, double>
#define x first
#define y second

using namespace std;

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

double sol,d,dist(punct,punct),X,Y;
punct p;
int n,k;
vector<punct > V;
set<punct > M;


int main()
{
    f>>n;
    for(;n;n--)
    {
        f>>X>>Y;
        V.push_back(make_pair(X,Y));
    }
    sort(V.begin(),V.end());
    sol = 2000000000.0*sqrt(2);
    for(auto it:V)
    {
        while(it.x-V[k].x>=sol)
        {
            M.erase(make_pair(V[k].y,V[k].x));
            k++;
        }
        p=make_pair(it.y,it.x);
        set<punct >::iterator j;
        j=M.lower_bound(make_pair(p.x-sol,p.y-sol));
        for(;j!=M.end()&&j->x<=p.x+sol;j++)
        {
            d=dist(p,*j);
            sol=min(sol,d);
        }
        M.insert(p);
    }
    g<<fixed<<setprecision(10)<<sol;
    return 0;
}
double dist(punct A, punct B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}