Pagini recente » Cod sursa (job #2054570) | Cod sursa (job #1566381) | Cod sursa (job #529764) | Istoria paginii runda/shiggydiggy123/clasament | Cod sursa (job #2072656)
#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;
}