Cod sursa(job #3277372)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 15 februarie 2025 21:06:39
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5;

int n;
pair<int,int> v[nmax + 5];

int rez = LLONG_MAX;

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

void solve(int st, int dr)
{
    if(st == dr)
    {
        return;
    }
    if(dr - st == 1)
    {
        rez = min(rez, dist(v[st], v[dr]));
        return;
    }
    int mij = (st + dr) >> 1;
    solve(st, mij);
    solve(mij + 1, dr);
    vector<pair<int,int>> p;
    for(int i=st;i<=dr;i++)
    {
        if((v[i].first - v[mij].first) * (v[i].first - v[mij].first) < rez)
        {
            p.push_back(v[i]);
        }
    }
    sort(p.begin(), p.end(), [](pair<int,int> a, pair<int,int> b){return a.second < b.second;});
    for(int i=0;i<p.size();i++)
    {
        for(int j=i+1;j<p.size();j++)
        {
            if((p[j].second - p[i].second) * (p[j].second - p[i].second) >= rez)
            {
                break;
            }
            rez = min(rez, dist(p[i], p[j]));
        }
    }
}

signed main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].first>>v[i].second;
    }
    sort(v + 1, v + n + 1);
    solve(1, n);
    long double rez_sq = sqrt(rez);
    cout<<fixed<<setprecision(7);
    cout<<rez_sq<<'\n';
    return 0;
}