Cod sursa(job #3281506)

Utilizator vali1234Danciu Valentin-Nicolae vali1234 Data 1 martie 2025 21:46:53
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 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");

bool cmpx(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.first < b.first;
}

bool cmpy(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.second < b.second;
}

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, double d) {
    double mindist = d;
    int size = v.size();
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            double dist = distanta(v[i], v[j]);
            mindist = std::min(mindist, dist);
        }
    }
    return mindist;
}

double apropiate_zona(const std::vector<std::pair<int, int>>& v, double d) {
    double mindist = d;
    int size = v.size();
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size && (v[j].second - v[i].second) < mindist; j++) {
            mindist = std::min(mindist, distanta(v[i], v[j]));
        }
    }
    return mindist;
}

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

    int mid = (left + right) / 2;
    double d1 = apropiate(v, left, mid, mindist);
    double d2 = apropiate(v, mid + 1, 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, 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;
    }

    std::sort(v.begin(), v.end(), cmpx);

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