Pagini recente » Cod sursa (job #428825) | Profil rauul | Cod sursa (job #2003760) | Monitorul de evaluare | Cod sursa (job #2488403)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <utility>
#include <iomanip>
using namespace std;
typedef long long int LLI;
const int NR_PCT = 7;
int DIM;
typedef pair<int,int> PUNCT;
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++){
int x,y;
fin >> x >> y;
vectorX.push_back(make_pair(x,y));
}
fin.close();
}
bool cmpY(PUNCT A, PUNCT B){
return A.second < B.second;
}
LLI calculDistanta(PUNCT &A, PUNCT &B){
return (A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second);
}
LLI dMinPuncte(vector <PUNCT> vectorX, int st, int dr){
LLI dMin = LONG_MAX;
if( dr - st <= 3){
int lim = dr - st;
for(int i = 0; i < lim - 1; i++)
for(int j = i + 1; j < lim; j++){
LLI tmp = calculDistanta(vectorX[i],vectorX[j]);
if(dMin > tmp)
dMin = tmp;
}
return dMin;
}
int indiceMediana = (st + dr) / 2;
LLI dMinSt = dMinPuncte(vectorX,0,indiceMediana);
LLI dMinDr = dMinPuncte(vectorX,indiceMediana+1,dr);
if (dMinSt > dMinDr)
dMin = dMinDr;
else
dMin = dMinSt;
vector <PUNCT> tmpY;
if(dr == DIM)
dr--;
for(int i = st; i < dr; i++)
if(vectorX[i+1].first - vectorX[i].first < dMin)
tmpY.push_back(vectorX[i]);
sort(tmpY.begin(),tmpY.end(),cmpY);
int lim = tmpY.size();
for(int i = 0; i < lim; i++){
for(int j = i + 1; j <= i + NR_PCT && j < lim; j++){
LLI 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());
ofstream fout("cmap.out");
fout << fixed << setprecision(6) << sqrt(dMinPuncte(vectorX,0,vectorX.size()));
fout.close();
return 0;
}