Cod sursa(job #1409625)

Utilizator andreimdvMoldovan Andrei andreimdv Data 30 martie 2015 17:02:44
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;

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

int n,a,b;
vector<pair<int,int> >v;

double dist(pair<int,int> a, pair<int,int>b)
{
    return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}

bool cmp(pair<int,int> a, pair<int,int> b)
{
    if(a.second<b.second)
        return true;
    if(a.second==b.second)
        if(a.first<b.first)
        return true;
    return false;
}

double solve(int l,int r)
{
    if(l==r) return 1<<30;
    if(r==l+1) return dist(v[l],v[r]);

    int mij=(l+r)/2;
    //divide et impera - o dreapta la mijloc ce imparte punctele in 2
    double sol=min(solve(l,mij),solve(mij+1,r));

    //cazul in care distanta minima este data de pct de o parte si de alta a dreptei,
    //se formeaza un dreptunghi de lungime 2 sol si latime sol centrat pe dreapta respectiva
    vector<pair<int,int> > aux;
    for(int i=l;i<=r;++i)
    {
        if(abs(v[i].first-v[mij].first)<sol) //pct la distanta mai mica de solutia actuala st si dr de dreapta
        {
            aux.push_back(v[i]);
        }
    }

    sort(aux.begin(),aux.end(),cmp); //dupa y
    for(int i=0;i<(int)aux.size();++i)
        for(int j=1;j<=7;++j)
            if(i+j<(int)aux.size())
            if(dist(aux[i],aux[i+j])<sol)
                sol=dist(aux[i],aux[i+j]);
    return sol;

}



int main()
{
    fin>>n;
    for(int i=1;i<=n;++i)
        {
            fin>>a>>b;
            v.push_back(make_pair(a,b));
        }
    sort(v.begin(),v.end());

    fout<<fixed<<setprecision(6)<<solve(1,n);

    return 0;
}