Cod sursa(job #2006356)

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

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

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

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

int solve(int left, int right, vector<pair<int,int>> &X, vector<pair<int, int>> &Y)
{
    if (right - left <= 3)
    {
        int 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;
    int 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 << sqrt(solve(1, N, X, Y));
    return 0;
}