Cod sursa(job #3341879)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 21 februarie 2026 13:52:59
Problema Cele mai apropiate puncte din plan Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const long long oo = 4e18;
const int NMax = 100000; int N,K;
pair <long long,long long> Point[NMax + 5],NewPoint[NMax + 5];
void Read()
{
    fin >> N;
    for(int i = 1; i <= N; ++i)
    {
        long long x,y;
        fin >> x >> y;
        Point[i] = make_pair(x,y);
    }
    sort(Point + 1, Point + N + 1);
}
long long dist(pair <long long,long long> a, pair <long long,long long> b)
{
    return 1LL * (a.first - b.first) * (a.first - b.first) + 1LL * (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, 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]));
    /*for(int i = 1; i <= K; ++i)
        for(int j = i + 1; j <= K; ++j)
            Min = min(Min, dist(NewPoint[i],NewPoint[j]));*/
    return Min;
}
int main()
{
    Read();
    fout << fixed << setprecision(6) << sqrt(DEI(1,N)) << "\n";
    /*long long Min = LLONG_MAX;
    for(int i = 1; i <= N; ++i)
        for(int j = i + 1; j <= N; ++j)
            Min = min(Min, dist(Point[i],Point[j]));
    fout << fixed << setprecision(6) << sqrt(Min) << "\n";*/
    return 0;
}