Cod sursa(job #2077866)

Utilizator maryan_lupMarian Lupascu maryan_lup Data 28 noiembrie 2017 18:07:34
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.4 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <utility>

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

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

int interclasare(int, int, int);

bool operator <= (std::pair<int, int> a, std::pair<int, int> b) {
    return a.second <= b.second;
}

void citire() {
    fin >> n;
    int x, y;
    for (int i = 1; i <= n; i++) {
        fin >> x >> y;
        V.emplace_back(x, y);
    }
}

bool cmp(const std::pair<int, int> &p1, const std::pair<int, int> &p2) {
    return (p1.second < p2.second);
}

long long distanta_euclidiana_la_patrat(const std::pair<int, int> &p1, const std::pair<int, int> &p2) {
    return (long long) (p1.first - p2.first) * (long long) (p1.first - p2.first) +
           (long long) (p1.second - p2.second) * (long long) (p1.second - p2.second);
}


long long Solve(int st, int dr) {

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

    int mij = (st + dr) / 2;

    long long d = std::min(Solve(st, mij), Solve(mij + 1, dr));

    std::vector<std::pair<int, int> > A;

    interclasare(st, mij, dr);

    for (int i = 0; i < V.size(); i++) {
        for (int j = i + 1; j <= i + 7 && j < V.size(); j++) {
            d = std::min(d, distanta_euclidiana_la_patrat(V[i], V[j]));
        }
    }
    return d;
}

int interclasare(int start, int m, int end) {
    std::vector <std::pair<int, int>> Aux;
    Aux.assign (V.size(), std::make_pair(0,0));
    int i = start, j = m + 1, k = 0, nr = 0;

    while ((i <= m) && (j <= end)) {
        if (V[i] <= V[j]) {
            Aux[k] = V[i];
            i++;
        } else {
            Aux[k] = V[j];
            j++;
        }
        k++;
    }
    while (i <= m) {
        Aux[k] = V[i];
        k++;
        i++;
    }
    while (j <= end) {
        Aux[k] = V[j];
        k++;
        j++;
    }
    for (i = start; i <= end; i++)
        V[i] = Aux[i - start];

    return nr;
}

int main() {
    citire();

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

    fout << std::fixed << std::setprecision(6) << sqrt(Solve(0, n-1)) << '\n';

    return 0;
}