Cod sursa(job #1275301)

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

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

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(double sol)
{
    std::ofstream out("cmap.out");
    out << std::setprecision(6) << std::fixed << sol << '\n';
    out.close();
}

double algo(const std::vector<std::pair<int, int> > &points, int left, int right)
{
    if (right - left < 5)
    {
        double d = dist(points[left], points[left + 1]);
        for (int i = left; i < right - 1; i++)
            for (int j = i + 1; j < right; j++)
                d = std::min(d, dist(points[i], points[j]));
        return d;
    }
    int m = left + (right - left) / 2;
    double dist1 = algo(points, left, m), dist2 = algo(points, m + 1, right), d = std::min(dist1, dist2);
    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++)
            if (i != j)
                d = std::min(d, dist(tmp[i], tmp[j]));
    return d;
}

bool mysort(const std::pair<int, int> &a, const std::pair<int, int> &b)
{
    if (a.first < b.first)
        return true;
    if (a.first == b.first)
        return a.second < b.second;
    return false;
}

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