Cod sursa(job #3327237)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 2 decembrie 2025 21:51:13
Problema Cele mai apropiate puncte din plan Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>

namespace geometric{
    const double Big = 1e10 + 0.1;
        struct point{
        int x, y;
    };
    double euclidean(const point& a, const point& b){
        return std::sqrt((a.x-b.x)*(a.x-b.x)+(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) 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 <= 15 ; ++j)
                    optimal = std::min(optimal,euclidean(points[i],points[j]));
        }
        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(7) << geometric::optimal_distance(points,0,n-1);
}