Pagini recente » Cod sursa (job #2277182) | Cod sursa (job #1456022) | Cod sursa (job #784566) | Cod sursa (job #1042345) | Cod sursa (job #3327263)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
namespace geometric{
struct point{
int x, y;
};
double euclidean(const point& a, const point& b){
return sqrtl(1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y));
}
double optimal_distance(const std::vector<point>& points,const int l,const int r){
double optimal = euclidean(points[l],points[r]);
if(r-l+1 <= 3){
for(int i = l ; i < r ; ++i)
for(int j = i+1 ; j <= r ; ++j)
optimal = std::fmin(optimal,euclidean(points[i],points[j]));
}else{
int mid = (l + r)/2;
std::vector<point> sorted;
optimal = std::fmin(optimal,optimal_distance(points,l,mid));
optimal = std::fmin(optimal,optimal_distance(points,mid+1,r));
for(int i = l ; i <= r ; ++i){
int difference = points[mid].x - points[i].x;
if(1.0 * difference < optimal)
sorted.push_back(points[i]);
}
std::sort(sorted.begin(),sorted.end(),
[&](const geometric::point& a, const geometric::point &b){return a.y < b.y;});
for(int i = 0 ; i < sorted.size() ; ++i)
for(int j = i + 1 ; j < sorted.size() && j - i <= 16 ; ++j)
optimal = std::fmin(optimal,euclidean(points[i],points[j]));
sorted.clear();
}
return optimal;
}
}
int main(void)
{
std::ifstream fileIn("cmap.in");
std::ofstream fileOut("cmap.out");
int n;
fileIn >> n;
std::vector<geometric::point> points(n);
for(int i = 0 ; i < n ; ++i)
fileIn >> points[i].x >> points[i].y;
std::sort(points.begin(),points.end(),
[&](const geometric::point& a, const geometric::point &b){return a.x < b.x;});
fileOut << std::fixed << std::setprecision(6) << geometric::optimal_distance(points,0,n-1);
}