Cod sursa(job #3358788)

Utilizator SGLDCASA SI PODUL SGLD Data 20 iunie 2026 13:45:17
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include<bits/stdc++.h>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
#define int long double
struct punct
{
    int a,b;
};
punct arr[100001];
int dist(int32_t idx1,int32_t idx2)
{
    return sqrt((arr[idx1].a-arr[idx2].a)*(arr[idx1].a-arr[idx2].a)+(arr[idx1].b-arr[idx2].b)*(arr[idx1].b-arr[idx2].b));
}
bool cmpa(punct c,punct d)
{
    return c.a<d.a;
}
bool cmpb(punct c,punct d)
{
    return c.b<d.b;
}
int vacucerescfraierilor(int32_t l,int32_t r)
{
    if(r-l+1<=3)
    {
        int mn=4e18;
        for(int i=l; i<=r; i++)
        {
            for(int j=i+1; j<=r; j++)
            {
                mn=min(mn,dist(i,j));
            }
        }
        sort(arr+l,arr+r+1,cmpb);
        return mn;
    }
    int32_t mid=+(r+l)/2;
    int lina=arr[mid].a;
    int st=vacucerescfraierilor(l,mid);
    int dr=vacucerescfraierilor(mid+1,r);
    int mnn=min(st,dr);
    inplace_merge(arr+l,arr+mid+1,arr+r+1,cmpb);
    vector<punct> inpatrat;
    for(int32_t i=l; i<=r; i++)
    {
        if(abs(arr[i].a-lina)<mnn)
        {
            inpatrat.push_back(arr[i]);
        }
    }
    for(int i=0; i<inpatrat.size(); i++)
    {
        for(int j=i+1; j<inpatrat.size() && inpatrat[j].b-inpatrat[i].b<mnn; j++)
        {
            mnn=min(mnn,sqrt((inpatrat[i].a-inpatrat[j].a)*(inpatrat[i].a-inpatrat[j].a)+(inpatrat[i].b-inpatrat[j].b)*(inpatrat[i].b-inpatrat[j].b)));
        }
    }
    return mnn;
}
signed main()
{
    int32_t n;
    in>>n;
    for(int32_t i=1; i<=n; i++)
    {
        in>>arr[i].a>>arr[i].b;
    }
    sort(arr+1,arr+n+1,cmpa);
    out<<fixed<<setprecision(6)<<vacucerescfraierilor(1,n);
    return 0;
}