Cod sursa(job #2488403)

Utilizator Marius92roMarius Marius92ro Data 6 noiembrie 2019 20:46:07
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <utility>
#include <iomanip>

using namespace std;

typedef long long int LLI;

const int NR_PCT = 7;
int DIM;

typedef pair<int,int> PUNCT;

void citire(vector <PUNCT> &vectorX){

    ifstream fin("cmap.in");

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

    fin >> DIM;

    for(int i = 1; i <= DIM; i++){
        int x,y;
        fin >> x >> y;
        vectorX.push_back(make_pair(x,y));
    }

    fin.close();
}

bool cmpY(PUNCT A, PUNCT B){
    return A.second < B.second;
}

LLI calculDistanta(PUNCT &A, PUNCT &B){

    return (A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second);

}

LLI dMinPuncte(vector <PUNCT> vectorX, int st, int dr){

    LLI dMin = LONG_MAX;

    if( dr - st <= 3){

        int lim = dr - st;  

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

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

                if(dMin > tmp)
                        dMin = tmp;
            }

        return dMin;
    }


    int indiceMediana = (st + dr) / 2;

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

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

    vector <PUNCT> tmpY;

    if(dr == DIM)
             dr--;

    for(int i = st; i < dr; i++)
        if(vectorX[i+1].first - vectorX[i].first < dMin)
                    tmpY.push_back(vectorX[i]);

    sort(tmpY.begin(),tmpY.end(),cmpY);

    int lim = tmpY.size();

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

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

            if(dMin > dTmp)
                  dMin = dTmp;

        }
    }

    return dMin;
}

int main(){

    vector <PUNCT> vectorX;
    citire(vectorX);

    sort(vectorX.begin(),vectorX.end());

    ofstream fout("cmap.out");
    fout << fixed << setprecision(6) << sqrt(dMinPuncte(vectorX,0,vectorX.size()));
    fout.close();

    return 0;

}