Cod sursa(job #3282917)

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

#define INF 100000000

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

        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[0], X[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);

            // impera
            for (int i = mid - 3; i < mid + 3; i++) {
                if (fabs(X[mid].first - X[i].first) < d) {
                    strip.push_back(X[i]);
                }
            }

            for (int i = 0; i < strip.size(); i++) {
                for (int j = 0; j < 6 && i + j < strip.size(); j++) {
                    double newDist = dist(strip[i], strip[i + j]);
                    if (newDist) {
                        d = std::min<double>(d, newDist);
                    }
                }
            }
            
            return d;
        }
    private: 
        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>> pairsY = pairs;

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

    fout << std::fixed << std::setprecision(6) << (new Solution())->divide(pairs, pairsY, 0, n, INF);
}