Cod sursa(job #3292506)

Utilizator Victor5539Tanase Victor Victor5539 Data 8 aprilie 2025 13:45:03
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#define int long long
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

const int MAX=1e5;
int n,i;
pair <int,int> p[MAX+5];

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);
}

bool compare(pair<int,int> a, pair<int,int> b)
{
    return a.first<b.first;
}

bool compare2(pair<int,int> a, pair<int,int> b)
{
    return a.second<b.second;
}

long double ans=1e18;

void solve(int st ,int dr)
{
    if (st==dr)
        return;

    int mij=(st+dr)>>1,x=p[mij].first,i,j;
    long double distanta;
    vector <pair <int,int > > pct;

    solve(st,mij);
    solve(mij+1,dr);

    for (i=st; i<=dr; i++)
    {
        if ((x-p[i].first)*(x-p[i].first)<=ans)
            pct.push_back(p[i]);
    }

    sort(pct.begin(),pct.end(),compare2);

    for (i=0; i<pct.size(); i++)
    {
        for (j=i+1; j<pct.size(); j++)
        {

            if ((pct[i].second-pct[j].second)*(pct[i].second-pct[j].second)>ans)
                break;

            distanta=dist(pct[i],pct[j]);

            ans=min(ans,distanta);
        }
    }
}

signed main()
{
    fin>>n;
    for (i=1; i<=n; i++)
        fin>>p[i].first>>p[i].second;

    sort(p+1,p+n+1,compare);


    solve(1,n);

    ans=sqrt(ans);

    fout<<fixed<<setprecision(7)<<ans;
    return 0;
}