Cod sursa(job #3194206)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 17 ianuarie 2024 11:56:42
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long long ll;
ll n,ans=1e18;
struct point
{
    ll x,y;
} v[100005];
bool byx(point a,point b)
{
    return a.x<b.x;
}
bool byy(point a,point b)
{
    return a.y<b.y;
}
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 st,ll dr)
{
    if(st==dr)
        return;
    ll mij=(st+dr)/2;
    ll x=v[mij].x;
    solve(st,mij);
    solve(mij+1,dr);
    vector<point> pts;
    for(int i=st;i<=dr;i++)
        if((v[i].x-x)*(v[i].x)<=ans)
            pts.push_back(v[i]);
    sort(pts.begin(),pts.end(),byy);
    for(int i=0;i<pts.size();i++)
    {
        for(int j=i+1;j<pts.size();j++)
        {
            if((pts[j].y-pts[i].y)*(pts[j].y-pts[i].y)>ans)
                break;
            ans=min(ans,dist(pts[i],pts[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);
    long double rez=sqrt((long double)ans);
    fout<<fixed<<setprecision(10)<<rez;
    return 0;
}