Pagini recente » Cod sursa (job #1160189) | Cod sursa (job #882456) | Cod sursa (job #1574968) | Cod sursa (job #1104136) | Cod sursa (job #2488374)
#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;
}