Cod sursa(job #3281508)

Utilizator vali1234Danciu Valentin-Nicolae vali1234 Data 1 martie 2025 21:54:22
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <cmath>
#include <float.h>
#include <iomanip>

#pragma GCC optimize("Ofast,unroll-loops")
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");

inline double distanta(const std::pair<int, int>& p1, const std::pair<int, int>& p2) {
    double dx = p1.first - p2.first;
    double dy = p1.second - p2.second;
    return sqrt(dx * dx + dy * dy);
}

double caz_de_baza(const std::vector<std::pair<int, int>>& v, int left, int right, double d) {
    double mindist = d;
    for (int i = left; i < right; i++) {
        for (int j = i + 1; j < right; j++) {
            mindist = std::min(mindist, distanta(v[i], v[j]));
        }
    }
    return mindist;
}

double apropiate_zona(std::vector<std::pair<int, int>>& vy, int left, int right, double d) {
    double mindist = d;
    int size = right - left;

    // Sort strip by Y-coordinate
    std::sort(vy.begin() + left, vy.begin() + right, [](const auto& a, const auto& b) {
        return a.second < b.second;
    });

    for (int i = left; i < right; i++) {
        for (int j = i + 1; j < right && (vy[j].second - vy[i].second) < mindist; j++) {
            mindist = std::min(mindist, distanta(vy[i], vy[j]));
        }
    }
    return mindist;
}

double apropiate(std::vector<std::pair<int, int>>& v, std::vector<std::pair<int, int>>& vy, int left, int right, double mindist) {
    if (right - left <= 2) {
        return caz_de_baza(v, left, right, mindist);
    }

    int mid = (left + right) / 2;
    double d1 = apropiate(v, vy, left, mid, mindist);
    double d2 = apropiate(v, vy, mid, right, mindist);
    double currentmind = std::min(d1, d2);

    std::vector<std::pair<int, int>> strip;
    for (int i = left; i < right; i++) {
        if (std::abs(v[i].first - v[mid].first) < currentmind) {
            strip.push_back(v[i]);
        }
    }

    return std::min(currentmind, apropiate_zona(strip, 0, strip.size(), currentmind));
}

int main() {
    int n;
    fin >> n;

    if (n < 2) {
        fout << "Insufficient points to calculate distance\n";
        return 0;
    }

    std::vector<std::pair<int, int>> v(n);
    for (int i = 0; i < n; i++) {
        fin >> v[i].first >> v[i].second;
    }

    // Sort by X-coordinate
    std::sort(v.begin(), v.end());

    // Copy sorted points for Y-sorting
    std::vector<std::pair<int, int>> vy = v;

    fout  << std::setprecision(6) << std::fixed<< apropiate(v, vy, 0, n, DBL_MAX);
    return 0;
}