Cod sursa(job #2875001)

Utilizator alexdumitrescuDumitrescu George Alex alexdumitrescu Data 20 martie 2022 17:09:24
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
#define ll long long
#define inf 4e18
#define pii pair<int, int>
#define sc second
#define fr first
#define mp make_pair
#define Nmax 100005

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

pii x[Nmax], y[Nmax], v[Nmax];
int n;

ll dist(pii a, pii b)
{
    return (ll)(a.fr-b.fr)*(a.fr-b.fr) + (ll)(a.sc-b.sc)*(a.sc-b.sc);
}

ll divide(int st, int dr)
{
    if(dr-st<1)
        return inf;
    if(st+1==dr)
    {
        if(y[st].fr>y[st+1].fr)
            swap(y[st], y[st+1]);
        return dist(x[st], x[dr]);
    }

    int mij=(st+dr)/2;
    ll d=min(divide(st, mij), divide(mij+1, dr));

    merge(y+st, y+mij+1, y+mij+1, y+dr+1, v);

    for(int i=0;i<dr-st+1;i++)
        y[st+i]=v[i];

    int k=0;
    for(int i=st;i<=dr;i++)
        if(abs(y[i].sc-x[mij].fr)<=d)
            v[++k]=y[i];

    for(int i=1;i<=k;i++)
        for(int j=i+1; j<=k && j-i<8 ; j++)
            d=min(d, dist(v[i], v[j]));

    return d;
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    fin >> n;
    for(int i=1;i<=n;i++)
        fin >> x[i].fr >> x[i].sc;

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

    for(int i=1;i<=n;i++)
    {
        y[i].fr=x[i].sc;
        y[i].sc=x[i].fr;
    }

    ll rez=divide(1, n);

    fout << fixed << setprecision(7) << sqrt(rez);
    return 0;
}