Pagini recente » Monitorul de evaluare | Cod sursa (job #1498517) | Cod sursa (job #1456074) | Cod sursa (job #1799359) | Cod sursa (job #3327253)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
namespace geometric{
const double Big = 1e12 + 0.1;
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 = Big;
if(r-l+1 <= 3){
for(int i = l ; i < r ; ++i)
for(int j = i+1 ; j <= r ; ++j)
optimal = std::min(optimal,euclidean(points[i],points[j]));
}else{
int mid = l + (r - l)/2;
std::vector<point> sorted;
optimal = std::min(optimal,optimal_distance(points,l,mid));
optimal = std::min(optimal,optimal_distance(points,mid+1,r));
for(int i = l ; i <= r ; ++i)
if(std::fabs(points[mid].x - points[i].x) < optimal)
sorted.emplace_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::min(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;
if(n <= 10000){
double optimal = geometric::euclidean(points[0],points[1]);
for(int i = 0 ; i < n ; ++i)
for(int j = i+1 ; j < n ; ++j)
if(geometric::euclidean(points[i],points[j]) < optimal)
optimal = geometric::euclidean(points[i],points[j]);
fileOut << std::fixed << std::setprecision(6) << optimal;
return 0;
}
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);
}