Cod sursa(job #1370744)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 3 martie 2015 16:52:32
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <cmath>

#define NMAX 100005
#define LL long long
#define INF 1000000000000000
using namespace std;

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

vector < pair <int, int> > X, Y, Aux;

LL dist(pair<int, int> &P, pair<int, int> &Q)
{
    return (LL)(P.first - Q.first) * (P.first - Q.first) + (LL)(P.second - Q.second) * (P.second - Q.second);
}

LL divide(int st, int dr)
{
    if (st >= dr - 1) return INF;
    if (dr - st == 2)
    {
        if (Y[st] > Y[st+1])
            swap(Y[st], Y[st+1]);
        return dist(X[st], X[st+1]);
    }

    int mij = st + ((dr - st) >> 1);
    LL best = min (divide(st, mij), divide(mij, dr));

    merge(Y.begin() + st, Y.begin() + mij, Y.begin() + mij, Y.begin() + dr, Aux.begin());
    copy(Aux.begin(), Aux.begin() + (dr - st), Y.begin() + st);

    int asize = -1;
    for (int i = st; i < dr; ++i)
        if (abs(Y[i].second - X[mij].first) <= best)
            Aux[++asize] = Y[i];
    for (int i = 0; i < asize; ++i)
        for (int j = i+1; (j < asize) && (j - i < 8); ++j)
            best = min(best, dist(Aux[i], Aux[j]));
    return best;
}
int main()
{
    int n;
    fin >> n;
    X.resize(n); Y.resize(n); Aux.resize(n);

    for (int i = 0; i < n; ++i)
        fin >> X[i].first >> X[i].second;
    sort(X.begin(), X.begin() + n);

    for (int i = 0; i < n; ++i)
        Y[i] = {X[i].second, X[i].first};

    fout << fixed << setprecision(6) << sqrt(divide(0, n)) << '\n';
    return 0;
}