Cod sursa(job #3317951)

Utilizator Tudor_ChelaruChelaru Tudor Tudor_Chelaru Data 26 octombrie 2025 11:23:39
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
int n,i;
long double ras;
struct pct{
    int x;
    int y;
};
bool compar(pct a,pct b)
{
    return (a.x<b.x) || (a.x==b.x && a.y>b.y);
}
bool compary(pct a,pct b)
{
    return (a.y>b.y);
}
pct v[100005];
long double dist(pct a,pct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void f(int st,int dr)
{
    long double m=0;
    int i,j;
    if(dr-st==1)
    {
        m=dist(v[st],v[dr]);
        if(ras<m)
        {
            ras=m;
        }
        return;
    }
    if(dr-st==2)
    {
        m=min(dist(v[st],v[st+1]),min(dist(v[st+1],v[st+2]),dist(v[st],v[st+2])));
        if(ras<m)
        {
            ras=m;
        }
        return;
    }
    f(st,(st+dr)/2);
    f((st+dr)/2,dr);
    vector<pct>p;
    for(j=(st+dr)/2-1;j>=1;j--)
    {
        if(v[(st+dr)/2].x-v[j].x<ras)
            p.push_back(v[j]);
        else
            break;
    }
    for(j=(st+dr)/2;j<=n;j++)
    {
        if(v[j].x-v[(st+dr)/2].x<ras)
        {
            p.push_back(v[j]);
        }
        else
            break;
    }
    sort(p.begin(),p.end(),compary);
    int l=p.size();
    for(j=0;j<=l-1;j++)
    {
        for(i=j+1;i<=j+7 && i<=n;i++)
        {
            if(dist(p[i],p[j])<ras)
            {
                ras=dist(p[i],p[j]);
            }
        }
    }
}
int main()
{
    ras=-1;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,compar);
    f(1,n);
    cout<<fixed<<setprecision(10)<<ras;
    return 0;
}