Cod sursa(job #3223034)

Utilizator unomMirel Costel unom Data 12 aprilie 2024 10:51:10
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>

using namespace std;

#define int long long

ifstream in("cmap.in");
ofstream out("cmap.out");
int n;
pair<int, int> v[100005];
pair<int, int> w[100005];
int INF = 2e9;

long double dist(pair<int, int> a, pair<int, int> b)
{
    return (long double)(sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)));
}

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    if(a.second == b.second)
    {
        return a.first < b.first;
    }

    return a.second < b.second;
}

long double solve(int st, int dr)
{
    if(st == dr)
    {
        return INF;
    }

    int mij = (st + dr) / 2;
    long double d1 = solve(st, mij);
    long double d2 = solve(mij + 1, dr);
    long double dmin = min(d1, d2);

    int cnt = 0;
    for(int i = st; i<=dr; i++)
    {
        if(abs(v[i].first - v[mij].first) <= dmin)
        {
            cnt++;
            w[cnt] = v[i];
        }
    }

    sort(w+1, w+cnt+1, cmp);

    for(int i = 1; i<=cnt; i++)
    {
        for(int j = i + 1; j<=cnt && dist(w[i], w[j]) <= dmin; j++)
        {
            dmin = min(dmin, dist(w[i], w[j]));
        }
    }


    return dmin;
}

signed main()
{
    in>>n;

    for(int i = 1; i<=n; i++)
    {
        in>>v[i].first>>v[i].second;
    }

    sort(v+1, v+n+1);

    out<<setprecision(6)<<fixed<<solve(1, n);

    return 0;
}