Cod sursa(job #1552280)

Utilizator ZimmyZimmermann Erich Zimmy Data 17 decembrie 2015 17:32:28
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define punct pair<double,double>
#define X first
#define Y second
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
vector<punct > v;
set<punct > M;
int n,i,j;
punct P;
double x,y,d;
double dist(punct A,punct B)
{
    return sqrt((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y));
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        v.push_back(make_pair(x,y));
    }
    sort(v.begin(),v.end());
    for(i=0;i<n;i++)
    {
        double aux=v[i].first;v[i].first=v[i].second;v[i].second=aux;
    }
    d=sqrt(2.0)*2000000000.0;
    M.insert(v[0]);
    for(i=0,j=1;j<n;j++)
    {
        for(;i<j;i++)
        {
            if(v[j].second-v[i].second<d)
                break;
            M.erase(v[i]);
        }
        P=make_pair(v[j].first-d,v[j].second-d);
        set<punct>::iterator it=M.lower_bound(P);
        for(;it->first-v[j].first<d&&it!=M.end();it++)
            d=min(d,dist(*it,v[j]));
        M.insert(v[j]);
    }
    g<<fixed<<setprecision(8)<<d;
    return 0;
}