Cod sursa(job #2488374)

Utilizator Marius92roMarius Marius92ro Data 6 noiembrie 2019 19:44:39
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cfloat>

using namespace std;

const int NR_PCT = 7; 

struct Punct{
    int x,y;
};

void citire(vector <Punct> &vectorX, vector <Punct> &vectorY){

    ifstream fin("cmap.in");

    if(!fin){
        cerr << "Eroare fisier";
        exit(EXIT_FAILURE);
    }

    int n;
    fin >> n;

    for(int i = 1; i <= n; i++){
        Punct aux;
        fin >> aux.x >> aux.y;

        vectorX.push_back(aux);
        vectorY.push_back(aux);
    }

    fin.close();

}

bool cmpX(Punct A, Punct B){
    return A.x < B.x;
}

bool cmpY(Punct A, Punct B){
    return A.y < B.y;
}

double calculDistanta(Punct A, Punct B){

    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));

}


double dMinPuncte(vector <Punct> vectorX, vector <Punct> vectorY, int st, int dr){

    
    double dMin = DBL_MAX;

    if( dr - st <= 3){  

        for(int i = 0; i < dr - st - 1; i++)
            for(int j = i + 1; j < dr - st; j++){

                double tmp = calculDistanta(vectorX[i],vectorX[j]);

                if(dMin > tmp)
                        dMin = tmp;
            }

        return dMin;
    }


    int indiceMediana = (st + dr) / 2;

    double dMinSt = dMinPuncte(vectorX,vectorY,0,indiceMediana);
    double dMinDr = dMinPuncte(vectorX,vectorY,indiceMediana+1,dr);

    if (dMinSt > dMinDr) 
                dMin = dMinDr;
    else
        dMin = dMinSt;

    int lim = vectorY.size();
    vector <Punct> tmpY;

    for(int i = 0; i < lim; i++)
        if(abs(vectorY[i].x - vectorX[indiceMediana].x) < dMin)
                    tmpY.push_back(vectorY[i]);

    lim = tmpY.size();

    for(int i = 0; i < lim; i++){
        for(int j = i + 1; j <= i + NR_PCT; j++){

            if(j >= lim )
                 continue;

            double dTmp = calculDistanta(tmpY[i],tmpY[j]);

            if(dMin > dTmp)
                  dMin = dTmp;

        }
    }

    return dMin;

}

int main(){

    vector <Punct> vectorX,vectorY;
    citire(vectorX,vectorY);

    sort(vectorX.begin(),vectorX.end(),cmpX);
    sort(vectorY.begin(),vectorY.end(),cmpY);

    ofstream fout("cmap.out");
    fout << dMinPuncte(vectorX,vectorY,0,vectorX.size());
    fout.close();

    return 0;

}