Pagini recente » Cod sursa (job #784272) | Cod sursa (job #184368) | Cod sursa (job #555609) | Cod sursa (job #1030909) | Cod sursa (job #2960410)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream cin ("cmap.in");
ofstream cout ("cmap.out");
vector<pair<long double , long double>> v;
bool cmp (pair<long double , long double> a , pair<long double , long double> b)
{
return a.first < b.first || (a.first == b.first && a.second < b.second);
}
bool cmp1(pair<long double , long double> a , pair<long double , long double> b)
{
return a.second < b.second || (a.second == b.second && a.first < b.first);
}
long double Distanta(pair<long double , long double> a , pair<long double , long double> b)
{
long double d1 = a.first - b.first;
long double d2 = a.second - b.second;
return sqrt(d1 * d1 + d2 * d2);
}
double MinDist(int l , int r)
{
if(r - l + 1 <= 3)
{
long double dist_min = 2e9;
for(int i = l ; i <= r ; ++i)
for(int j = i+1 ; j <= r ; ++j)
dist_min = min(dist_min , Distanta(v[i] , v[j]));
return dist_min;
}
else
{
int mid = (l+r) / 2;
long double dist_min = min(MinDist(l , mid) , MinDist(mid+1 , r));
vector<pair<long double , long double>> puncte;
for(int i = l ; i <= r ; ++i)
if(abs(v[i].first - v[mid].first <= dist_min))
puncte.push_back(v[i]);
sort(puncte.begin() , puncte.end() , cmp1);
for(int i = 0 ; i < puncte.size() ; ++i)
for(int j = i+1 ; j < puncte.size() && j <= i+8 ; ++j)
dist_min = min(dist_min , Distanta(puncte[i] , puncte[j]));
return dist_min;
}
}
int main()
{
int n;
cin >> n;
for(int i = 1 ; i <= n ; ++i)
{
int x , y;
cin >> x >> y;
v.push_back({x , y});
}
sort(v.begin() , v.end() , cmp);
cout << fixed << setprecision(6) << MinDist(0 , n-1);
}