Pagini recente » Cod sursa (job #199706) | Cod sursa (job #295075) | Cod sursa (job #1290475) | Cod sursa (job #1355882) | Cod sursa (job #2488380)
#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, vector <Punct> &vectorY){
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);
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;
}
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, vector <Punct> vectorY, 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,vectorY,0,indiceMediana);
ULLI dMinDr = dMinPuncte(vectorX,vectorY,indiceMediana+1,dr);
if (dMinSt > dMinDr)
dMin = dMinDr;
else
dMin = dMinSt;
vector <Punct> tmpY;
for(int i = 0; i < DIM; i++)
if(abs(vectorY[i].x - vectorX[indiceMediana].x) < dMin)
tmpY.push_back(vectorY[i]);
int lim = tmpY.size();
for(int i = 0; i < lim; i++){
for(int j = i + 1; j <= i + NR_PCT; j++){
if(j >= lim )
continue;
ULLI 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 << sqrt(dMinPuncte(vectorX,vectorY,0,vectorX.size()));
fout.close();
return 0;
}