Cod sursa(job #2005792)

Utilizator FredyLup Lucia Fredy Data 28 iulie 2017 11:17:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.1 kb
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <fstream>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

#define int long long

int n,k,a,b;
double dminr;

double dist(pair <int, int> A, pair <int, int> B)
{
    double d;
    long long v;
    v=((long long)(A.first-B.second)*(long long)(A.first-B.second)+(long long)(A.second-B.first)*(long long)(A.second-B.first));
    d=sqrt((double)v);
    return d;
}

vector <pair <int, int> > PX;
set <pair <int, int> > SY;
set <pair <int, int> > :: iterator it,cit;

#undef int
int main()
{
    #define int long long
    fin>>n;
    for (int i=1;i<=n;i++)
    {
        long long x,y;
        fin>>x>>y;
        PX.push_back(make_pair(x,y));
    }
    sort(PX.begin(),PX.end());
    dminr=10000000.0;
    k=0;
    SY.insert(make_pair(PX[0].second,PX[0].first));
    for (int i=1;i<n;i++)
    {
        /// unele puncte prea departate pot fi sterse din SY si trecut de ele in PX
        while (1)
        {
            if (k==i)
                break;
            if (PX[i].first-PX[k].first>dminr)
            {
                SY.erase(make_pair(PX[k].second,PX[k].first));
                k++;
            }
            else
                break;
        }
        /// trebuie obtinute punctele din SY care sunt la departare <= dminr pe oY
        SY.insert(make_pair(PX[i].second,PX[i].first));
        it=SY.lower_bound(make_pair(PX[i].second,PX[i].first));
        cit=it;
        /// 4 puncte situate in jos
        if (cit!=SY.begin())
        {
            cit--;
            if (dist(PX[i],*cit)<dminr)
            {
                dminr=dist(PX[i],*cit);

            }
        }
        if (cit!=SY.begin())
        {
            cit--;
            if (dist(PX[i],*cit)<dminr)
            {
                dminr=dist(PX[i],*cit);

            }
        }
        if (cit!=SY.begin())
        {
            cit--;
            if (dist(PX[i],*cit)<dminr)
            {
                dminr=dist(PX[i],*cit);

            }
        }
        if (cit!=SY.begin())
        {
            cit--;
            if (dist(PX[i],*cit)<dminr)
            {
                dminr=dist(PX[i],*cit);

            }
        }
        /// 4 puncte situate in sus
        cit=it;
        cit++;
        if (cit!=SY.end())
            if (dist(PX[i],*cit)<dminr)
            {
                dminr=dist(PX[i],*cit);

                cit++;
            }
        if (cit!=SY.end())
            if (dist(PX[i],*cit)<dminr)
            {
                dminr=dist(PX[i],*cit);

                cit++;
            }
        if (cit!=SY.end())
            if (dist(PX[i],*cit)<dminr)
            {
                dminr=dist(PX[i],*cit);

                cit++;
            }
        if (cit!=SY.end())
            if (dist(PX[i],*cit)<dminr)
            {
                dminr=dist(PX[i],*cit);

                cit++;
            }
    }

    fout<<setprecision(6)<<fixed<<dminr;
    return 0;
}