Cod sursa(job #2672380)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 13 noiembrie 2020 20:16:27
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;

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

int n;
vector<pair<int, int>> X, Y, v;

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

int solve(vector<pair<int, int>> X, vector<pair<int, int>> Y, int l, int r)
{
    if(l == r - 1)
        return dist(X[l], X[l + 1]);

    if(l == r - 2)
        return min(dist(X[l], X[l + 1]), dist(X[l + 1], X[l + 2]));

    int mid = (l + r) / 2;
    int best = min(solve(X, Y, l, mid), solve(X, Y, mid, r));

    sort(Y.begin() + l, Y.begin() + r);

    v.clear();

    for(int i = l; i <= r; i++)
        if(abs(Y[i].first - X[mid].first) < best)
            v.emplace_back(Y[i].first, Y[i].second);

    int len = v.size();

    for(int i = 0; i < len; i++)
        for(int j = i + 1; j < len && j - i < 8; j++)
            best = min(best, dist(v[i], v[j]));

    return best;
}

int main()
{
    in >> n;

    for(int i = 0; i < n; i++)
    {
        int x, y;
        in >> x >> y;

        X.emplace_back(x, y);
    }

    sort(X.begin(), X.end());

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

    out << fixed << setprecision(6) << sqrt(solve(X, Y, 0, n - 1)) << '\n';

    return 0;
}