Pagini recente » Cod sursa (job #918681) | Cod sursa (job #721359) | Cod sursa (job #1765610) | Cod sursa (job #363684) | Cod sursa (job #1026279)
#include <fstream>
#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(){
ifstream in("cmap.in");
in>>n;
for (int i=0; i<n; ++i){
int x,y;
in>>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);
}
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+st,puncte+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 = dr-st+1;
for (i=0; i<sirSize; ++i)
puncte[i+st] = sir[i];
sir.clear();
for(int i=st;i <dr; ++i)
for (int j=i+1; j<dr && (j-i)<8;++j){
long long d = distanta(puncte[i],puncte[j]);
dMin = min(d,dMin);
}
return dMin;
}
}
int main(){
getData();
sort(puncte, puncte+n, compAbs);
ofstream out("cmap.out");
long long d = divide(0,n-1);
out<<setprecision(10)<<sqrt(d);
return 0;
}