Cod sursa(job #810687)

Utilizator psycho21rAbabab psycho21r Data 10 noiembrie 2012 19:19:28
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <utility>

using namespace std;

typedef long long i64;

const i64 INF = 4e18;
const i64 MAX_N = 100000;

vector<pair<i64, i64> > V(MAX_N), X, Y;

i64 dist(const pair <i64, i64> a, const pair <i64, i64> b)
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

i64 cmap(int left, int right)
{
    if(right - left <= 1)
        return INF;
    if(right - left == 2)
    {
        if(Y[left] > Y[left + 1])
            swap(Y[left], Y[left + 1]);
        return dist(X[left], X[left + 1]);
    }
    int mid = (left + right)/2;
    i64 best = min(cmap(left, mid), cmap(mid, right));

    merge(Y.begin() + left, Y.begin() + mid, Y.begin() + mid, Y.begin() + right, V.begin());
    copy(V.begin(), V.begin() + (right - left), Y.begin() + left);

    int v_size = 0;
    for(int i = 0; i < right; ++i)
        if (abs(Y[i].second - X[mid].first) <= best)
            V[v_size++] = Y[i];
    for(int i = 0; i < v_size - 1; ++i)
        for(int j = i + 1; j < v_size && j - i < 8; ++j)
            best = min(best, dist(V[i], V[j]));
    return best;
}

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

    int N;
    in >> N;
    X.resize(N);
    Y.resize(N);
    for(int i = 0; i < N; ++i)
        in >> X[i].first >> X[i].second;
    sort(X.begin(), X.end());
    for(int i = 0; i < N; ++i)
        Y[i] = make_pair(X[i].second, X[i].first);

    out << fixed << sqrt(cmap(0, N));

    in.close();
    out.close();
    return 0;
}