Cod sursa(job #3282931)

Utilizator BuzatuCalinBuzatu Calin BuzatuCalin Data 7 martie 2025 16:11:29
Problema Cele mai apropiate puncte din plan Scor 55
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

#define INF 10000000

class Solution {
    public:
        std::vector<std::pair<double, double>> Y;

        double divide(std::vector<std::pair<double, double>>& X, int left, int right, double d) {
            if (right - left < 2) {
                return INF;
            }
            if (right - left == 2) {
                return dist(X[left], X[left + 1]);
            }
            
            int mid = (left + right) / 2;
            double d1 = divide(X, left, mid, d);
            double d2 = divide(X, mid, right, d);
            d = std::min(d1, d2);
            
            Y.clear();
            for (int i = left; i < right && Y.size() < 6; i++) {
                if (fabs(X[i].first - X[mid].first) < d) {
                    Y.push_back(X[i]);
                }
            }
    
            std::sort(Y.begin(), Y.end(), [](const auto& a, const auto& b) {
                return a.second < b.second;
            });
            
            double newDist = 0;
            for (int i = 0; i < Y.size(); i++) {
                for (int j = 1; j < 6 && i + j < Y.size(); j++) {
                    newDist = dist(Y[i], Y[i + j]);
                    if (newDist) {
                        d = std::min<double>(d, newDist);
                    }
                }
            }

            return d;
        }
    private: 
        inline double dist(std::pair<double, double>& a, std::pair<double, double>& b) {
            return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
        }
};

int main() {
    std::ifstream fin("cmap.in");
    std::ofstream fout("cmap.out");

    int n, x, y;
    std::vector<std::pair<double, double>> pairs;

    fin >> n;
    for (int i = 0; i < n; i++) {
        fin >> x >> y;
        pairs.push_back({x, y});
    }

    sort(pairs.begin(), pairs.end());

    Solution solution;
    fout << std::fixed << std::setprecision(6) << solution.divide(pairs, 0, n, INF);
}