Cod sursa(job #3282855)

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

#define INF 10000000

class Solution {
    public:
        static double divide( std::vector<std::pair<double, double>> &X, 
            std::vector<std::pair<double, double>> &Y, 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, Y, left, mid, d);
            double d2 = divide(X, Y, mid, right, d);
            d = std::min(d1, d2);

            std::vector<std::pair<double, double>> strip;
            for (auto p : Y) {
                if (std::fabs(p.first - X[mid].first) < d) {
                    strip.push_back(p);
                }
            }

            for (int i = 0; i < strip.size(); i++) {
                for (int j = 1; j < 6 && i + j < strip.size(); j++) {
                    d = std::min(d, dist(strip[i], strip[i + j]));
                }
            }
            
            return d;
        }

        static 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});
    }

    std::vector<std::pair<double, double>> X = pairs, Y = pairs;

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

    sort(Y.begin(), Y.end(), [](std::pair<double, double> a, std::pair<double, double> b) { 
        return a.second < b.second;
    });

    fout << std::fixed << std::setprecision(6) << Solution::divide(X, Y, 0, X.size() - 1, INF);
}