Pagini recente » Cod sursa (job #2503987) | Cod sursa (job #704364) | Cod sursa (job #1651485) | Cod sursa (job #46692) | Cod sursa (job #2989477)
#include<fstream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iomanip>
#define vi vector<int>
#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 , vi &v){
int S = r - l + 1 , i , j;
double ans = 1e18;
if(S <= 3){
for(i = l ; i <= r ; ++ i){
for(j = i + 1 ; j <= r ; ++ j){
ans = min(ans , dist(idx[i] , idx[j]));
}
v.push_back(idx[i]);
}
sort(v.begin() , v.end() , crt2);
return ans;
}
int m = (l + r) >> 1;
vi L , R;
ans = min(solve(l , m , L) , solve(m + 1 , r , R));
i = j = 0;
while(i < L.size() && j < R.size()){
if(Y[L[i]] < Y[R[j]])
v.push_back(L[i++]);
else
v.push_back(R[j++]);
}
while(i < L.size()){
v.push_back(L[i++]);
}
while(j < R.size()){
v.push_back(R[j++]);
}
for(i = 0 ; i < S ; ++ i){
for(j = i + 1 ; j < min(S , i + 8) ; ++ j){
ans = min(ans , dist(v[i] , v[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);
vi CV;
fout << fixed << setprecision(6) << solve(1 , N , CV) << '\n';
return 0;
}