Cod sursa(job #3183555)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 12 decembrie 2023 11:18:27
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long long ll;
typedef long double ld;
ll ans=1e18;
int n;
struct point
{
    ll x,y;
} v[100005];
bool byx(point a,point b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
bool byy(point a,point b)
{
    if(a.y!=b.y)
        return a.y<b.y;
    return a.x<b.x;
}
ll dist(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void solve(ll l,ll r)
{
    if(r-l+1<=3)
    {
        for(int i=l;i<r;i++)
            for(int j=i+1;j<=r;j++)
                ans=min(ans,dist(v[i],v[j]));
        return;
    }
    int mij=(l+r)/2;
    solve(l,mij);
    solve(mij+1,r);
    int myx=(v[mij].x+v[mij+1].x)/2;
    int d=sqrt(ans);
    vector<point> a;
    for(int i=l;i<=r;i++)
        if(abs(v[i].x-myx)<=d)
            a.push_back(v[i]);
    sort(a.begin(),a.end(),byy);
    for(int i=0;i<a.size();i++)
    {
        for(int j=i+1;j<a.size()&&abs(a[j].y-a[i].y)<=d;j++)
            ans=min(ans,dist(a[i],a[j]));
        for(int j=i-1;j>=0&&abs(a[j].y-a[i].y)<=d;j--)
            ans=min(ans,dist(a[i],a[j]));
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,byx);
    solve(1,n);
    ld rez=sqrt(ld(ans));
    fout<<fixed<<setprecision(10)<<rez;
    return 0;
}