Cod sursa(job #1275299)

Utilizator sunt_emoSunt emo sunt_emo Data 24 noiembrie 2014 23:15:16
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

inline long long dist(const std::pair<int, int> &a, const std::pair<int, int> &b)
{
    return (((long long) a.first) - b.first) * (((long long) a.first) - b.first) + (((long long) a.second) - b.second) * (((long long) a.second) - b.second);
}

std::vector<std::pair<int, int> >read_data()
{
    std::ifstream in("cmap.in");
    int n, x, y;
    std::vector<std::pair<int, int> > ret;
    in >> n;
    while (n--)
    {
        in >> x >> y;
        ret.push_back(std::pair<int, int>(x, y));
    }
    in.close();
    return ret;
}

void write_data(long long sol)
{
    std::ofstream out("cmap.out");
    out << std::setprecision(6) << std::fixed << sqrt(sol) << '\n';
    out.close();
}

long long algo(const std::vector<std::pair<int, int> > &points, int left, int right)
{
    if (right - left < 2)
        return -1;
    if (right - left == 2)
        return dist(points[left], points[left + 1]);
    int m = left + (right - left) / 2;
    long long dist1 = algo(points, left, m), dist2 = algo(points, m, right), d;
    if (dist1 != -1 && dist2 != -1)
        d = std::min(dist1, dist2);
    else if (dist1 == -1 && dist2 == -1)
    {
        return std::min(std::min(dist(points[left], points[m]), dist(points[left], points[right - 1])), dist(points[m], points[right - 1]));
    }
    else
        d = dist1 == -1 ? dist2 : dist1;
    std::vector<std::pair<int, int> > tmp;
    for (int i = left; i < right; i++)
        if (dist(points[i], points[m]) < d)
            tmp.push_back(points[i]);
    for (int i = 0; i < (int) tmp.size() - 1; i++)
        for (int j = i + 1; j < std::min((int) tmp.size(), i + 8); j++)
            d = std::min(d, dist(tmp[i], tmp[j]));
    return d;
}

int main()
{
    std::vector<std::pair<int, int> > points = read_data();
    std::sort(points.begin(), points.end());
    write_data(algo(points, 0, points.size()));
}