Cod sursa(job #2369496)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 6 martie 2019 00:02:39
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>

#define llg long long
#define llg_pair std::pair <llg, llg>
#define x  first
#define y second

llg dist2(const llg_pair& p0, const llg_pair& p1) {
    return (p0.y - p1.y) * (p0.y - p1.y) + (p0.x - p1.x) * (p0.x - p1.x);
}

#define MAXN           100005
#define INF 40000000000000005

int N;

#define _Middle (Left+Right)/2

std::vector <llg_pair> V(MAXN);
std::vector <llg_pair> A, B;

llg DivideEtImpera(int Left = 0, int Right = N, std::vector <llg_pair>& A = A, std::vector <llg_pair>& B = B) {
    if (Left+1 >= Right) return INF;
    if (Left+2 == Right) {
        if (B[Left] > B[Left+1])
            std::swap(B[Left], B[Left+1]);
        return dist2(A[Left], A[Left+1]);
    }   llg Min = std::min(DivideEtImpera(Left, _Middle, A, B), DivideEtImpera(_Middle, Right, A, B));

    std::merge(B.begin() + Left, B.begin() + _Middle, B.begin() + _Middle, B.begin() + Right, V.begin());
    std::copy(V.begin(), V.begin() + (Right-Left), B.begin() + Left);

    int replace = 0;
    for (int i=Left, j; i<Right; ++i)
        if (abs(B[i].second - A[_Middle].first) <= Min)
            V[replace++] = B[i];

    for (int i=0, j; i<replace; ++i)
        for (j=i+1; j<replace && j < i+8; ++j)
            Min = std::min(Min, dist2(V[j], V[i]));
    return Min;
}

std::ifstream In ("cmap.in");
std::ofstream Out("cmap.out");

void Citire() {
    In >> N;
    for (int i=0, X, Y; i<N; ++i)
        In >> X >> Y, A.push_back({X, Y});
}

void Rezolvare() {
    std::sort(A.begin(), A.end());
    for (int i=0; i<N; ++i)
        B.push_back(A[i]);
    Out << std::fixed << std::setprecision(6) << sqrt(double(DivideEtImpera())) << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}