Pagini recente » Cod sursa (job #2681805) | Cod sursa (job #1656534) | Cod sursa (job #1989238) | Cod sursa (job #1946736) | Cod sursa (job #2989458)
#include<fstream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iomanip>
#define sq(x) (1.0*(x)*(x))
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int const D = 1e5 + 3;
int N;
int X[D] , Y[D] , idx[D];
bool crt(int i , int j){
return X[i] < X[j];
}
bool crt2(int i , int j){
return Y[i] < Y[j];
}
double dist(int i , int j){
return sqrt(sq(X[i] - X[j]) + sq(Y[i] - Y[j]));
}
double solve(int l , int r){
int S = r - l + 1 ;
double ans = 1e18;
if(S <= 3){
for(int i = l ; i <= r ; ++ i){
for(int j = i + 1 ; j <= r ; ++ j){
ans = min(ans , dist(idx[i] , idx[j]));
}
}
return ans;
}
int m = (l + r) >> 1;
ans = min(solve(l , m) , solve(m + 1 , r));
vector<int> p;
for(int i = l ; i <= r ; ++ i)
p.push_back(idx[i]);
sort(p.begin() , p.end());
for(int i = 0 ; i < S ; ++ i){
for(int j = i + 1 ; j < min(S , i + 8) ; ++ j){
ans = min(ans , dist(p[i] , p[j]));
}
}
return ans;
}
int main(){
fin >> N;
for(int i = 1 ; i <= N ; ++ i){
fin >> X[i] >> Y[i];
idx[i] = i;
}
sort(idx + 1 , idx + 1 + N , crt);
fout << fixed << setprecision(6) << solve(1 , N) << '\n';
return 0;
}