Pagini recente » Cod sursa (job #1152241) | Cod sursa (job #3152794) | Cod sursa (job #828055) | Cod sursa (job #3193826) | Cod sursa (job #2980028)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
const int dim = 1e5 + 5;
const long double INF = 1e9;
struct Vect
{
int row , col;
};
int n;
Vect v[dim];
bool cmp (Vect a , Vect b)
{
return a.row < b.row || (a.row == b.row && a.col < b.col);
}
bool cmp1 (Vect a , Vect b)
{
return a.col < b.col || (a.col == b.col && a.row < b.row);
}
long double Dist(Vect a , Vect b)
{
long double d1 = a.row - b.row;
long double d2 = a.col - b.col;
return sqrt(d1 * d1 + d2 * d2);
}
long double DivideEtImpera(int l , int r)
{
if(r - l + 1 <= 3)
{
long double dist_min = INF;
for(int i = l ; i <= r ; ++i)
for(int j = i + 1 ; j <= r ; ++j)
dist_min = min(dist_min , Dist(v[j] , v[i]));
return dist_min;
}
else
{
int mid = (l + r) / 2;
long double dist_min = min(DivideEtImpera(l , mid) , DivideEtImpera(mid + 1 , r));
vector<Vect> p;
for(int i = l ; i <= r ; ++i)
if(abs(v[i].row - v[mid].row) <= dist_min)
p.push_back(v[i]);
sort(p.begin() , p.end() , cmp1);
for(int i = 0 ; i < p.size() ; ++i)
for(int j = i + 1 ; j < p.size() && j - i + 1 <= 9 ; ++j)
dist_min = min(dist_min , Dist(p[i] , p[j]));
return dist_min;
}
}
int main()
{
fin >> n;
for(int i = 1 ; i <= n ; ++i)
fin >> v[i].row >> v[i].col;
sort(v + 1 , v + n + 1 , cmp);
fout << fixed << setprecision(6) << DivideEtImpera(1 , n);
}