Cod sursa(job #1191022)

Utilizator darrenRares Buhai darren Data 26 mai 2014 11:28:21
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cmath>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>

using namespace std;

const double INF = 1e10;

int N;
vector<pair<int, int> > A, B;

inline double q_dist(const pair<int, int>& p1, const pair<int, int>& p2)
{
    return sqrt(1.0 * (p1.first - p2.first) * (p1.first - p2.first) + 1.0 * (p1.second - p2.second) * (p1.second - p2.second));
}
double get_dist(int i1, int i2)
{
    if (i1 == i2) return INF;
    if (i1 + 1 == i2) return q_dist(A[i1], A[i2]);

    int mid = (i1 + i2) / 2;

    int xn = A[mid].first;
    double d1 = get_dist(i1, mid), d2 = get_dist(mid + 1, i2);
    double dnow = min(d1, d2);

    B.clear();
    for (int i = 0; i < int(A.size()); ++i)
        if (A[i].first >= xn - dnow && A[i].first <= xn + dnow)
            B.push_back(make_pair(A[i].second, A[i].first));
    sort(B.begin(), B.end());

    for (int i = 0; i < int(B.size()); ++i)
        for (int j = 1; i + j < int(B.size()) && j <= 8; ++j)
            dnow = min(dnow, q_dist(B[i], B[i + j]));

    return dnow;
}

int main()
{
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");

    fin >> N;
    for (int i = 1; i <= N; ++i)
    {
        A.push_back(make_pair(0, 0));
        fin >> A.back().first >> A.back().second;
    }
    sort(A.begin(), A.end());

    fout << fixed << setprecision(8) << get_dist(0, int(A.size()) - 1) << '\n';

    fin.close();
    fout.close();
}