Cod sursa(job #3282849)

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

#define INF 100000

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[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
            std::vector<std::pair<double, double>> strip;
            for (int i = left; i < right; i++) {
                if (X[mid].first - d <= X[i].first && X[i].first <= X[mid].first + d) {
                    strip.push_back(X[i]);
                }
            }

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

        static 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(), [](std::pair<double, double> a, std::pair<double, double> b) { 
        return a.first < b.first;
    });

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

    fout << std::setprecision(8) << Solution::divide(X, Y, 0, X.size(), INF);
}