Cod sursa(job #1191036)

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

using namespace std;

const long long INF = (1LL << 60);

int N;
vector<pair<int, int> > A;
pair<int, int> B[100002], C[100002];
int sz;

inline long long q_dist(const pair<int, int>& p1, const pair<int, int>& p2)
{
    return 1LL * (p1.first - p2.first) * (p1.first - p2.first) + 1LL * (p1.second - p2.second) * (p1.second - p2.second);
}
long long 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;
    long long d1 = get_dist(i1, mid), d2 = get_dist(mid + 1, i2);
    long long dnow = min(d1, d2);

    merge(A.begin() + i1, A.begin() + mid + 1, A.begin() + mid + 1, A.begin() + i2 + 1, B);

    sz = 0;
    for (int i = 0; i < i2 - i1 + 1; ++i)
        if (B[i].second >= xn - dnow && B[i].second <= xn + dnow)
            C[++sz] = B[i];

    for (int i = 1; i <= sz; ++i)
        for (int j = 1; i + j <= sz && j <= 7; ++j)
            dnow = min(dnow, q_dist(C[i], C[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());

    for (int i = 0; i < int(A.size()); ++i)
        swap(A[i].first, A[i].second);

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

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