Cod sursa(job #2064860)

Utilizator datsickBaciu Dan Stefan datsick Data 12 noiembrie 2017 22:33:33
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <utility>
#include <cmath>
#include <iomanip>
#define INT_MAX 1000001
using namespace std;

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

vector < pair <int,int> > myVect;
vector < int > sideLane;

bool cmp (const int a, const int b)
{
    return myVect[a].first<myVect[b].first;
}

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));
}

double cmap(int left, int right)
{
    //cazul in care am mai putin de un punct
    if(left>=right)
    {
        double bestsol=INT_MAX;
        return bestsol;
    }
    //2 sau 3 puncte ramase
    else if (right - left <= 2)
    {
        double bestsol=INT_MAX;
        for(int i = left; i <= right; ++i)
        {
            for(int j = i+1; j <= right; ++j) if(dist(myVect[i] , myVect[j]) < bestsol)
                bestsol=dist(myVect[i] , myVect[j]);
        }
        return bestsol;
    }
    int mid = (left + right)/2;
    double bestsol = min(cmap(left,mid),cmap(mid,right));

    sideLane.clear();

    //prelucram sirul de care se situeaza la distanta maxima la stanga si la dreapta dreptei
    for(int i = mid; i >= left && myVect[mid].first-myVect[i].first <= bestsol; i--) sideLane.push_back(i);
    for(int i = mid+1; i <= right && myVect[i].first-myVect[mid].first <= bestsol; i++) sideLane.push_back(i);

    sort(sideLane.begin(),sideLane.end(),cmp);

    for(int i=0; i<sideLane.size()-1; ++i)
        for(int j=i+1; j<=i+7 && j<sideLane.size(); ++j)
            if(dist(myVect[sideLane[i]],myVect[sideLane[j]]) < bestsol)
            bestsol=dist(myVect[sideLane[i]],myVect[sideLane[j]]);
    return bestsol;
}

int main()
{
    int n;
    fin>>n;
    int x,y;
    for(int i=0;i<n;i++)
    {
        fin>>x>>y;
        myVect.push_back(make_pair(x,y));
    }
    sort(myVect.begin(),myVect.end());
    fout<<fixed<<setprecision(6)<<cmap(0,n-1);
}