Pagini recente » Cod sursa (job #2542643) | Cod sursa (job #1684794) | Cod sursa (job #54217) | Cod sursa (job #2484427) | Cod sursa (job #1028531)
#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(maxn);
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){
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));
sort(Y.begin()+st,Y.begin()+dr);
int size_Z=0;
for(int i = st;i<dr;i++)
if(abs(Y[i].second - X[mij].first)<=rez)
Z[size_Z++] = Y[i];
for(int i=0;i<size_Z -1; ++i){
for(int j=i+1;j<size_Z && j-i<8; ++j)
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;
}