Cod sursa(job #3292985)

Utilizator andrei1232008nicolae andrei andrei1232008 Data 9 aprilie 2025 22:19:39
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int lim=1e5;
int n,i;
long double t;
struct punct
{
    long double x,y;
}v[lim+10];
bool cmp(punct a,punct b)
{
    return a.x<b.x;
}
bool cmpi(punct a,punct b)
{
    return a.y<b.y;
}
long double dist(int x,int y,int x2,int y2)
{
    return ((x-x2)*(x-x2)+(y-y2)*(y-y2));
}
void solve(int st,int dr)
{
    if(st==dr)
        return;
    int mid=(st+dr)/2,i,x=v[mid].x,j;
    solve(st,mid);
    solve(mid+1,dr);
    vector <punct> a;
    for(i=st;i<=dr;i++)
    {
        if((v[i].x-x)*(v[i].x-x)<=t)
            a.push_back(v[i]);
        else break;
    }
    sort(a.begin(),a.end(),cmpi);
    int l=a.size();
    for(i=0;i<l-1;i++)
        for(j=i+1;j<l;j++)
    {
        if((a[i].y-a[j].y)*(a[i].y-a[j].y)>t)break;
        t=min(t,dist(a[i].x,a[i].y,a[j].x,a[j].y));
    }
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp);
    t=1e18;
    solve(1,n);
    t=sqrt(t);
    fout<<fixed<<setprecision(6)<<t;
    return 0;
}