Cod sursa(job #2070351)

Utilizator BogdanMacoMacovei Bogdan BogdanMaco Data 19 noiembrie 2017 14:27:24
Problema Cele mai apropiate puncte din plan Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;

int n;
vector <pair<int, int>> V;

void citire(const char* fileName)
{
    ifstream in (fileName);
    in >> n;
    int x, y;
    for (int i = 1; i <= n; i++)
    {
        in >> x >> y;
        V.push_back({x, y});
    }

    in.close();
}

long long dist2 (pair<int, int> p1, pair<int, int> p2)
{
    return (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}

long long solutie (int st, int dr)
{

    if (dr - st == 1)
    {
        return dist2 (V[st], V[dr]);
    }

    else if (dr - st == 2)
    {
        return min(dist2(V[st], V[st + 1]), min(dist2(V[st], V[st + 2]), dist2(V[st + 1], V[st + 2])));
    }

    int mij = (st + dr) / 2;

    long long d = min(solutie (st, mij), solutie (mij + 1, dr));

    vector<pair<int, int>> A;

    int delta = (int) ceil (sqrt (d));

    for (unsigned i = st; i <= dr; i++)
        if (abs(V[i].first - V[mij].first) <= delta)
            A.push_back(V[i]);

    sort (A.begin(), A.end(), [](pair <int, int> p1, pair <int, int> p2) -> bool {
            return p1.second < p2.second;
    });

    for (unsigned i = 0; i < A.size(); i++)
        for (unsigned j = i + 1; j <= i + 7 && j < A.size(); j++)
            d = min(d, dist2(A[i], A[j]));

    return d;
}

int main()
{
    citire("cmap.in");

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

    ofstream out ("cmap.out");
    out << fixed << setprecision(6) << sqrt (solutie (0, n-1)) << '\n';
    out.close();
    return 0;
}