Pagini recente » Cod sursa (job #2649482) | Cod sursa (job #2202731) | Cod sursa (job #3208279) | Cod sursa (job #2188085) | Cod sursa (job #1028728)
#include <iostream>
#include <fstream>
#define maxn 100001
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define INF 1<<30
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
vector<pair <int,int> > X,Y,Z;
int n;
double dist(const pair<int,int> &A, const pair<int,int> &B){
return sqrt((A.first - B.first)*(A.first - B.first)+(A.second-B.second)*(A.second-B.second));
}
double DivConq(int st, int dr, vector<pair<int,int> > &X, vector<pair<int,int> > &Y){
int j;
int q;
if (st>=dr)
return INFINITY;
if(st+1 == dr)
return dist(X[st],X[dr]);
int mij = (st+dr)/2;
double rez = min(DivConq(st,mij,X,Y),DivConq(mij+1,dr,X,Y));
int size_Z = 0;
for(int i=mij;i>=st;i--)
if(X[mij].first - X[i].first <= rez)
Z.push_back(X[i]);
for(int i=mij+1;i<=dr;i++)
if(X[mij].first - X[i].first <= rez)
Z.push_back(X[i]);
sort(Z.begin(), Z.end());
for(int i=1;i<=size_Z;i++){
for(j = i + 1, q = 1; j <= Z.size() && q <= 6; ++j, ++q){
rez = min(rez,dist(Z[i],Z[j]));
}
}
return rez;
}
int main()
{
f >> n;
int a,b;
for(int i=0;i<n;i++){
f >> a >> b;
X.push_back(make_pair(a,b));
}
sort(X.begin(),X.end());
for(int i=0;i<X.size();i++){
Y.push_back(make_pair(X[i].second, X[i].first));
}
g << setprecision(8) << DivConq(0,n-1,X,Y);
return 0;
}