Cod sursa(job #3341870)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 21 februarie 2026 13:24:11
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int oo = INT_MAX;
const int NMax = 100000; int N,K;
pair <int,int> Point[NMax + 5],NewPoint[NMax + 5];
void Read()
{
    fin >> N;
    for(int i = 1; i <= N; ++i)
    {
        int x,y;
        fin >> x >> y;
        Point[i] = make_pair(x,y);
    }
    sort(Point + 1, Point + N + 1);
}
long long 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) ;
}
long long DEI(int Left, int Right)
{
    if (Left == Right)
        return oo;
    if (Left == Right-1)
        return dist(Point[Left],Point[Right]);
    int Mid = (Left + Right) / 2;
    long long A = DEI(Left,Mid);
    long long B = DEI(Mid + 1, Right);
    long long Min = min(A,B);
    for(int i = Left,K = 0; i <= Right; ++i)
    {
        if( abs(Point[i].first-Point[Mid].first)< Min)
            NewPoint[++K]= make_pair(Point[i].second,Point[i].first);
    }

    sort(NewPoint + 1, NewPoint + K + 1);

    for(int i = 1; i <= K; ++i)
        for(int j = i + 1; j <= K && (j-i) < 8; ++j)
            Min = min(Min, dist(NewPoint[i],NewPoint[j]));

    return Min;
}
int main()
{
    Read();
    fout << fixed << setprecision(6) << sqrt(DEI(1,N)) << "\n";
    return 0;
}