Cod sursa(job #2567304)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 3 martie 2020 16:32:14
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

#define llg     long long
#define ldb     long double
#define EPS     1e-6

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

ldb dist(int x0, int y0, int x1, int y1) {
    ldb ans = (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);
    return sqrt(ans);
}
ldb dist(std::pair <int, int> &p0, std::pair <int, int> &p1) {
    return dist(p0.first, p0.second, p1.first, p1.second);
}
llg dist2(int x0, int y0, int x1, int y1) {
    llg ans = (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);
    return ans;
}
llg dist2(std::pair <int, int> &p0, std::pair <int, int> &p1) {
    return dist2(p0.first, p0.second, p1.first, p1.second);
}

#define FILENAME    std::string("cmap")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int32_t main()
{
    input >> N;
    V.resize(N);
    for (auto &it:V) input >> it.first >> it.second;
    std::sort(V.begin(), V.end());

    int ptr = 0;
    int best1 = -1, best2 = -1;
    llg min;
    for (int i=0; i<V.size(); ++i) {
        if (best1 > -1) while ((V[i].first - V[ptr].first)*(V[i].first - V[ptr].first) > min) ++ ptr;
        for (int j=ptr; j<i; ++j)
            if (best1 == -1 || dist2(V[j], V[i]) < min)
                best1 = j, best2 = i, min = dist2(V[best1], V[best2]);
    }   output << std::fixed << std::setprecision(6) << dist(V[best1], V[best2]) << '\n';

    return 0;
}