Pagini recente » Cod sursa (job #56995) | Cod sursa (job #1212872) | Cod sursa (job #3267197) | Cod sursa (job #2038661) | Cod sursa (job #1026264)
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
const int INF = (1<<30);
const int Nmax = 100000;
int n;
pair<int, int> puncte[Nmax];
void getData(){
freopen("cmap.in","r",stdin);
scanf("%d",&n);
for (int i=0; i<n; ++i){
int x,y;
scanf("%d %d",&x, &y);
puncte[i]=pair<int, int>(x,y);
}
}
bool compAbs(const pair<int, int>& A, const pair<int, int>& B ){
return (A.first < B.first);
}
bool compOrd(const pair<int, int>& A, const pair<int, int>& B) {
return (A.second < B.second);
}
double distanta(const pair<int, int>&A, const pair<int, int>& B){
int x = (A.first-B.first)*(A.first-B.first);
int y = (A.second-B.second) * (A.second-B.second);
return sqrt(1.0*x+1.0*y);
}
double divide(const int& st, const int& dr){
if ( dr - st <=2){
// sunt pe cazul |p| <=3, caut cea mai apropiata pereche;
double dMin = INF;
for (int i = st; i<dr; ++i){
for (int j = i+1; j<=dr; ++j){
double aux = distanta(puncte[i],puncte[j]);
dMin = min(dMin, aux);
}
}
//sortam submultimi dupa ordonata
sort(puncte+st,puncte+dr+1,compOrd);
return dMin;
}else {
int mij = (st+dr)/2;
vector< pair<int, int> > sir;
double s1 = divide(st,mij);
double s2 = divide (mij+1,dr);
double dMin = min(s1,s2);
int i = st, j = mij+1;
//INTERCLASRE:
while (i<=mij && j<=dr)
if( compOrd(puncte[i],puncte[j])==true){
sir.push_back(puncte[i]);
++i;
}else{
sir.push_back(puncte[j]);
++j;
}
while (i<=mij) {
sir.push_back(puncte[i]);
++i;
}
while (j<=dr){
sir.push_back(puncte[j]);
++j;
}
//Distanta:
int sirSize = sir.size();
for(int i=0; i<sirSize; ++i)
for (int j=i+1; j<sirSize && (j-i)<8;++j){
double d = distanta(sir[i],sir[j]);
dMin = min(d,dMin);
}
sir.clear();
return dMin;
}
}
int main(){
getData();
sort(puncte, puncte+n, compAbs);
freopen("cmap.out","w",stdout);
double d = divide(0,n-1);
printf("%0.6f",d);
return 0;
}