Cod sursa(job #2345592)

Utilizator _Tudor_Tudor C _Tudor_ Data 16 februarie 2019 15:07:24
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("rmq.in");
ofstream fout("rmq.out");
const int oo = 1e9;
const int NMax = 100000;
int N, k;
pair<int, int> P[NMax + 5], X[NMax + 5];

void Read()
{
    fin >> N;
    for(int i = 0; i < N; i++)
        fin >> P[i].first >> P[i].second;
    sort(P + 1, P + N + 1);
}

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 DEI(int Left, int Right)
{
    if(Right == Left)
        return oo;
    if(Right == Left + 1)
        return Dist(P[Left], P[Right]);

    int Mid = (Left + Right) / 2;
    int A = DEI(Left, Mid);
    int B = DEI(Mid + 1, Right);
    int Min = min(A, B);
    k = 0;
    for(int i = Left; i <= Right; i++)
        if(abs(P[i].first - P[Mid].first) <= Min)
            X[++k] = P[i];
    for(int i = 1; i <= k; i++)
        for(int j = i + 1; j <= k; j++)
            if(Dist(X[i], X[j]) < Min)
                Min = Dist(X[i], X[j]);
    return Min;
}


int main()
{
    Read();
    fout << fixed << setprecision(6) << sqrt(DEI(1, N));
}