Cod sursa(job #1172219)

Utilizator tudorv96Tudor Varan tudorv96 Data 17 aprilie 2014 00:18:58
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

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

const int N = 1e5 + 5;

typedef long long ll;
const ll oo = 1e18;

vector <pair <ll, ll> > V(N), X, Y;
int n;

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

ll divideEtImpera(int st, int dr, vector <pair <ll, ll> > &X, vector <pair <ll, ll> > &Y) {
    if (dr - st <= 1)
        return oo;
    if (dr - st == 2) {
        if (Y[st] > Y[st+1])
            swap (Y[st], Y[st+1]);
        return dist(X[st], X[st+1]);
    }
    int mid = (st + dr) >> 1;
    ll best = min(divideEtImpera(st, mid, X, Y), divideEtImpera(mid, dr, X, Y));
    merge (Y.begin() + st, Y.begin() + mid, Y.begin() + mid, Y.begin() + dr, V.begin());
    copy (V.begin(), V.begin() + dr - st, Y.begin() + st);
    int sz = 0;
    for (int i = st; i < dr; ++i)
        if (abs (Y[i].second - X[mid].first) <= best)
            V[sz++] = Y[i];
    for (int i = 0; i < sz - 1; ++i)
        for (int j = i + 1; j < sz && j - i <= 8; ++j)
            best = min(best, dist(V[i], V[j]));
    return best;
}

int main() {
    fin >> n;
    for (int i = 0; i < n; ++i) {
        ll x, y;
        fin >> x >> y;
        X.push_back (make_pair (x, y));
    }
    sort (X.begin(), X.end());
    for (vector <pair <ll, ll> > :: iterator it = X.begin(); it != X.end(); ++it)
        Y.push_back (make_pair (it->second, it->first));
    fout << setprecision(8) << sqrt(divideEtImpera(0, X.size(), X, Y));
}