Cod sursa(job #1581989)

Utilizator proflaurianPanaete Adrian proflaurian Data 27 ianuarie 2016 15:17:11
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <iomanip>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#define punct pair<int,int>

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
punct v[100010];
set<punct>M;
int i,n,a,b,k;
double d,dist(punct,punct);
int main()
{
    f>>n;
    for(i=0;i<n;i++)
    {
        f>>a>>b;
        v[i]=make_pair(a,b);
    }
    sort(v,v+n);
    d=2000000001.0*sqrt(2.0);
    M.insert(make_pair(v[0].second,v[0].first));
    for(i=1;i<n;i++)
    {
        for(;(double)(v[i].first-v[k].first)>d;k++)
            M.erase(make_pair(v[k].second,v[k].first));
        punct P=make_pair(v[i].second,v[i].first);
        set<punct>::iterator
           is=M.lower_bound(make_pair((int)(P.first-d-1),-1000000001));
        for(;is!=M.end()&&(double)(is->first-P.first)<=d;is++)
            d=min(d,dist(*is,P));
        M.insert(P);
    }
    g<<fixed<<setprecision(10)<<d;
    return 0;
}
double dist(punct A,punct B)
{
    double
    xa=(double)A.first,
    xb=(double)B.first,
    ya=(double)A.second,
    yb=(double)B.second;
    return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}