Pagini recente » Cod sursa (job #171329) | Cod sursa (job #2952879) | Cod sursa (job #1362117) | Cod sursa (job #1477971) | Cod sursa (job #2488383)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <limits.h>
using namespace std;
typedef unsigned long long int ULLI;
const int NR_PCT = 7;
int DIM;
struct Punct{
int x,y;
};
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++){
Punct aux;
fin >> aux.x >> aux.y;
vectorX.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;
}
ULLI calculDistanta(Punct A, Punct B){
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
ULLI dMinPuncte(vector <Punct> vectorX, int st, int dr){
ULLI dMin = ULONG_MAX;
if( dr - st <= 3){
for(int i = 0; i < dr - st - 1; i++)
for(int j = i + 1; j < dr - st; j++){
ULLI tmp = calculDistanta(vectorX[i],vectorX[j]);
if(dMin > tmp)
dMin = tmp;
}
return dMin;
}
int indiceMediana = (st + dr) / 2;
ULLI dMinSt = dMinPuncte(vectorX,0,indiceMediana);
ULLI dMinDr = dMinPuncte(vectorX,indiceMediana+1,dr);
if (dMinSt > dMinDr)
dMin = dMinDr;
else
dMin = dMinSt;
vector <Punct> tmpY;
int lim = vectorX.size();
for(int i = st; i < dr && i < lim - 1; i++)
if(vectorX[i+1].x - vectorX[i].x < dMin)
tmpY.push_back(vectorX[i]);
sort(tmpY.begin(),tmpY.end(),cmpY);
lim = tmpY.size();
for(int i = 0; i < lim; i++){
for(int j = i + 1; j <= i + NR_PCT && j < lim; j++){
ULLI 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(),cmpX);
ofstream fout("cmap.out");
cout << sqrt(dMinPuncte(vectorX,0,vectorX.size()));
fout.close();
return 0;
}