Pagini recente » Cod sursa (job #818480) | Cod sursa (job #187102) | Cod sursa (job #277399) | Cod sursa (job #938695) | Cod sursa (job #1046622)
#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;
int n;
bool dupay(pair<int,int> Q, pair<int,int>R){
return Q.second < R.second;
}
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){
int j,q;
vector<pair<int,int> > Z;
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),DivConq(mij+1,dr,X));
for(int i=st;i<=dr;i++)
if(abs(X[mij].first - X[i].first) <=rez)
Z.push_back(X[i]);
sort(Z.begin(), Z.end(),dupay);
for(int i=1;i<Z.size();i++){
for(j = i + 1; j <= Z.size() && (j-i) < 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());
g << setprecision(8) << DivConq(0,n-1,X);
return 0;
}