Cod sursa(job #3204277)

Utilizator amunnumeVlad Patrascu amunnume Data 16 februarie 2024 09:43:32
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct elem
{
    ll x,y;
}v[N];
ll n,i,j,t;
long double rez;
bool cmp1(elem a,elem b)
{
    return a.x<b.x;
}
bool cmp2(elem a,elem b)
{
    return a.y<b.y;
}
ll dist(elem a,elem b)
{
    return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y);
}
void solve(ll st,ll dr)
{
     ll mid=(st+dr)>>1;
     if(st==dr) return;
     ll x=v[mid].x;
     solve(st,mid);
     solve(mid+1,dr);
     vector<elem> a;
     for(i=st;i<=dr;i++)
     {
         if(1ll*(v[i].x-x)*(v[i].x-x)<=t) a.push_back(v[i]);
     }
     sort(a.begin(),a.end(),cmp2);
     int m=a.size();
     for(i=1;i<m-1;++i)
     for(j=i+1;j<=m-1;++j)
     {
        if(1ll*(a[j].y-a[i].y)*(a[j].y-a[i].y)>t)
            break;
        t=min(t,dist(a[i],a[j]));
     }
}
int main()
{
    fin>>n; t=1e18;
    for(i=1;i<=n;++i)
    {
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp1);
    solve(1,n);
    rez=sqrt((long double)t);
    fout<<fixed<<setprecision(6)<<rez;
    return 0;
}