Cod sursa(job #2006363)

Utilizator sfechisalin@yahoo.comSfechis Alin [email protected] Data 29 iulie 2017 15:49:21
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <bits/stdc++.h>

#define x first
#define y second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

typedef long long i64;

int N;
vector<pair<i64, i64>>X;
vector<pair<i64,i64>>Y;
vector<pair<i64, i64>> aux;

i64 Distance(pair<i64, i64> p1, pair<i64, i64> p2)
{
    return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
}

i64 solve(int left, int right, vector<pair<i64,i64>> &X, vector<pair<i64, i64>> &Y)
{
    if (right - left <= 3)
    {
        i64 answ;
        for (int i = left; i < right; ++i)
            for (int j = i + 1; j <= right; ++j)
            {
                if (Y[i] > Y[j])
                    swap(Y[i], Y[j]);
                 answ = min(answ, Distance(X[i], X[j]));
            }
        return answ;
    }

    int mid = (left + right) >> 1;
    i64 best = min(solve(left, mid, X, Y), solve(mid + 1, right, X, Y));

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

    int _size = 0;
    for (int i = left; i <= right; ++i)
        if (abs(X[mid].x - Y[i].y) <= best)
            aux[_size++ ] = Y[i];

    for (int i = 0; i < _size - 1; ++i)
        for (int j = i + 1; j < _size && j - i < 8; ++j)
                best = min(best, Distance(aux[i], aux[j]));
    return best;
}

int main()
{
    fin >> N;
    X.resize(N + 1);
    Y.resize(N + 1);
    aux.resize(N + 1);
    for (int i = 1; i <= N; ++i)
        fin >> X[i].x >> X[i].y;

    sort(X.begin(), X.end());
    for (int i = 1;i <= N; ++i)
        Y[i] = {X[i].y, X[i].x};

    fout << fixed << setprecision(6) << sqrt(solve(1, N, X, Y)) << "\n";
    return 0;
}