Pagini recente » Cod sursa (job #706316) | Cod sursa (job #747910) | Cod sursa (job #136408) | Cod sursa (job #1266132) | Cod sursa (job #980639)
Cod sursa(job #980639)
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
typedef std::pair<int,int> Point;
const int MAX_N(100001);
const double MAX_VALUE(1 << 30);
int n;
Point v [MAX_N];
double Result(MAX_VALUE);
inline void Read (void)
{
std::freopen("cmap.in","r",stdin);
std::scanf("%d\n",&n);
for (int i(1) ; i <= n ; ++i)
std::scanf("%d %d\n",&v[i].first,&v[i].second);
std::fclose(stdin);
}
inline void Print (void)
{
std::freopen("cmap.out","w",stdout);
std::printf("%.6lf",Result);
std::fclose(stdout);
}
inline double EuclidianDistance (Point a, Point b)
{
return std::sqrt(static_cast<unsigned long long>(std::abs(a.first - b.first)) * static_cast<unsigned long long>(std::abs(a.first - b.first)) + static_cast<unsigned long long>(std::abs(a.second - b.second)) * static_cast<unsigned long long>(std::abs(a.second - b.second)));
}
double Compute (int left, int right)
{
if (left >= right)
return MAX_VALUE;
if (left == right - 1)
return EuclidianDistance(v[left],v[right]);
int mid((left + right) >> 1);
double min(std::min(Compute(left,mid),Compute(mid + 1,right)));
std::vector<Point> r;
int i;
for (i = left ; i <= right ; ++i)
if (i != mid)
if (std::abs(v[mid].first - v[i].first) < min)
r.push_back(v[i]);
int j, end;
std::sort(r.begin(),r.end(), [ ] (Point a, Point b) {return a.second < b.second;});
for (i = 0 ; i < r.size() ; ++i)
for (j = i + 1 ; j <= i + 8 && j < r.size() ; ++j)
min = std::min(min,EuclidianDistance(r[i],r[j]));
return min;
}
int main (void)
{
Read();
std::sort(v + 1,v + n + 1);
Result = Compute(1,n);
Print();
return 0;
}