Cod sursa(job #2072656)

Utilizator dark_knight2012Potec Tiberiu dark_knight2012 Data 22 noiembrie 2017 01:10:22
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.39 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <float.h>
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;

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

struct punct
{
    int x;
    int y;
};

int comparare_x(punct a, punct b)
{
    return a.x < b.x;
}

int comparare_y(punct a, punct b)
{
    return a.y < b.y;
}

float distanta_euclidiana(punct a, punct b)
{
    float x = a.x-b.x;
    float y = a.y-b.y;
    float distanta;
    distanta = pow(x,2) + pow(y,2);
    distanta =  sqrt(distanta);
    return distanta;
}

int citire(vector <punct> &vx, vector <punct> &vy)
{
    int n;
    in >> n;
    for (int i = 0; i < n; i++)
    {
        punct aux;
        in >> aux.x;
        in >> aux.y;
        vx.push_back(aux);
    }
    sort(vx.begin(), vx.end(), comparare_x);
    vy=vx;
    return 1;
}

int afisare(vector <punct> vx)
{
    for (auto it : vx)
    {
        out << it.x << " " << it.y << endl;
    }
    return 1;
}

float calculare_distanta_minima(vector <punct> &vx, int left, int right, vector <punct> &vy)
{
    if(right-left == 1) /// daca avem doar un punct la un anume moment
    {
        return INT_MAX;
    }
    if(right-left == 2) /// daca avem doua puncte la un anume moment
    {
        if(vy.at(left).y>vy.at(left+1).y)
            swap(vy.at(left),vy.at(left+1));
        return distanta_euclidiana(vx.at(0),vx.at(1));
    }

    int mij =  (left + right) / 2; /// impartim vectorul in 2

    float distanta_minima_stanga = calculare_distanta_minima(vx, left, mij, vy); /// calculam recursiv distanta minima din partea stanga a vectorului
    float distanta_minima_dreapta = calculare_distanta_minima(vx, mij, right, vy); /// calculam recursiv distanta minima din partea dreapta a vectorului
    float distanta_minima_temporara = min(distanta_minima_stanga, distanta_minima_dreapta); /// luam minimul distantelor dintre cele doua valori calculate anterior

    vector<punct> puncte_auxiliare(right-left);
    merge(vy.begin()+left, vy.begin()+mij, vy.begin()+mij, vy.begin()+right, puncte_auxiliare.begin(), comparare_y);
    copy(puncte_auxiliare.begin(), puncte_auxiliare.begin()+(right-left), vy.begin()+left);


    vector <punct> aux;
    for (int i = left; i < right; i++) /// parcurgem elementele din vy
    {
        if (abs(vy.at(i).x - vx.at(mij).x) <= distanta_minima_temporara) /// in aux le bagam doar pe cele care au distanta de la coordonata x la mijloc (la mediana verticala) mai mica ca distanta_minima_temporara
        {
            aux.push_back(vy.at(i));
        }
    }

    float distanta_minima_finala = distanta_minima_temporara; /// presupunem ca distanta minima finala este egala cu cea temporara

    for(int i=0; i<aux.size(); i++)
    {
        for(int j=i+1; j<aux.size() && aux.at(j).y - aux.at(i).y <= distanta_minima_temporara; j++)
        {
            float distanta_auxiliara = distanta_euclidiana(aux.at(i),aux.at(j));
            if(distanta_auxiliara < distanta_minima_finala)
            {
                distanta_minima_finala = distanta_auxiliara;
            }
        }
    }
    return distanta_minima_finala;
}



int main()
{
    vector <punct> vx;
    vector <punct> vy;
    citire(vx, vy);
    //afisare(vy);
    out<<fixed;
    out<<setprecision(6)<<calculare_distanta_minima(vx,0,vx.size(),vy);
    return 0;
}