Cod sursa(job #2921414)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 30 august 2022 21:28:16
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;
int n;
pair <int,int> v[100001],inv[100001],vec[100001];
long long 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);
}
long long solve(int st,int dr)
{
    if(dr-st==1)
        return dist(v[st],v[st+1]);
    if(dr-st==2)
        return min(min(dist(v[st],v[st+1]),dist(v[st+1],v[st+2])),dist(v[st],v[st+2]));
    int mij=(st+dr)/2;
    long long delta=min(solve(st,mij),solve(mij+1,dr));
    sort(inv+st,inv+dr+1);
    int cnt=0;
    for(int i=st;i<=dr;i++)
        if(inv[i].second>=v[mij].first-delta&&inv[i].second<=v[mij].first+delta)
            vec[++cnt]=inv[i];
    for(int i=1;i<=cnt;i++)
        for(int j=i+1;j<=min(i+5,cnt);j++)
            delta=min(delta,dist(vec[i],vec[j]));
    return delta;
}
int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    int i;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i].first>>v[i].second;
    sort(v+1,v+n+1);
    for(i=1;i<=n;i++)
        inv[i]={v[i].second,v[i].first};
    cout<<fixed<<setprecision(8)<<sqrt(solve(1,n));
    return 0;
}