Cod sursa(job #2064182)

Utilizator aaether14Dinescu Stefan Cristian aaether14 Data 11 noiembrie 2017 21:56:10
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <vector>
#include <algorithm>
#include <fstream>
#include <limits>
#include <cmath>
#include <iomanip>

using point = std::pair<double, double>;
using pointArr = std::vector<point>;

double squaredDistance(const point& p1, const point& p2) {
    return std::pow(p1.first - p2.first, 2) + std::pow(p1.second - p2.second, 2);
}

double solve(pointArr& points, int left, int right) {
    if (left >= right) {
        return std::numeric_limits<double>::max();
    }
    else if (right - left == 1) {
        if (points[left].second > points[right].second) {
            std::swap(points[left], points[right]);
        }
        return squaredDistance(points[left], points[right]);
    }
    auto middle = (left + right) >> 1; 
    auto minLeft = solve(points, left, middle);
    auto minRight = solve(points, middle + 1, right);
    auto delta = std::min(minLeft, minRight);
    pointArr candidates;
    for (auto it = left; it <= right; ++it) {
        if (std::abs(points[it].first - points[middle].first) <= delta) {
            candidates.push_back(points[it]);
        }
    }
    for(auto it = 0; it < candidates.size(); ++it) {
        for (auto it2 = it + 1; it2 < candidates.size() && it2 - it < 6; ++it2) {
            delta = std::min(delta, squaredDistance(candidates[it], candidates[it2]));
        }
    }
    return delta;
}

int main()
{
    pointArr points;
    std::ifstream fin("cmap.in");
    auto n = 0; fin >> n;
    for (auto it = 0; it < n; ++it) {
        point currentPoint;
        fin >> currentPoint.first >> currentPoint.second;
        points.push_back(currentPoint);
    }
    fin.close();
    std::sort(points.begin(), points.end());
    std::ofstream fout("cmap.out");
    fout << std::fixed << std::setprecision(6) << std::pow(solve(points, 0, points.size() - 1), 0.5);;
    fout.close();
    return 0;
}