Pagini recente » Cod sursa (job #1144144) | Cod sursa (job #1941680) | Cod sursa (job #1663780) | Cod sursa (job #637397) | Cod sursa (job #1026238)
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
const int INF = (1<<30);
int n;
vector <pair<int, int> > puncte;
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.push_back(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);
}
long long distanta(const pair<int, int>&A, const pair<int, int>& B){
long long x = (A.first-B.first)*(A.first-B.first);
long long y = (A.second-B.second) * (A.second-B.second);
return (x+y);
}
long long divide(const int& st, const int& dr){
if ( dr - st <=2){
// sunt pe cazul |p| <=3, caut cea mai apropiata pereche;
long long dMin = INF;
for (int i = st; i<dr; ++i){
for (int j = i+1; j<=dr; ++j){
long long aux = distanta(puncte[i],puncte[j]);
dMin = min(dMin, aux);
}
}
//sortam submultimi dupa ordonata
sort(puncte.begin()+st,puncte.begin()+dr+1,compOrd);
return dMin;
}else {
int mij = (st+dr)/2;
vector< pair<int, int> > sir;
long long s1 = divide(st,mij);
long long s2 = divide (mij+1,dr);
long long 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){
long long d = distanta(sir[i],sir[j]);
dMin = min(d,dMin);
}
return dMin;
}
}
int main(){
getData();
sort(puncte.begin(), puncte.end(), compAbs);
freopen("cmap.out","w",stdout);
printf("%0.6f",sqrt(divide(0,n-1)));
return 0;
}