Cod sursa(job #3277370)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 15 februarie 2025 21:01:56
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 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 (a.first - b.first) * (a.first - b.first) + (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((v[j].second - v[i].second) * (v[j].second - v[i].second) >= rez)
            {
                break;
            }
            rez = min(rez, dist(v[i], v[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;
}