Cod sursa(job #1191025)

Utilizator darrenRares Buhai darren Data 26 mai 2014 11:32:15
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 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;
pair<int, int> B[100002];
int sz;

inline double q_dist(const pair<int, int>& p1, const pair<int, int>& p2)
{
    return 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);

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

    for (int i = 1; i <= sz; ++i)
        for (int j = 1; i + j <= sz && j <= 7; ++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) << sqrt(get_dist(0, int(A.size()) - 1)) << '\n';

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