Cod sursa(job #3294292)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 21 aprilie 2025 00:16:40
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
//https://infoarena.ro/job_detail/3293467?action=view-source
#include <bits/stdc++.h>
#define VMAX 100005
#define INF 200000000000000000
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");

struct pct{
long long int i,j;
};
vector<pct> puncte;
long long int dist_min=INF;

bool comp(pct a, pct b)
{
    return a.j<b.j || a.j==b.j && a.i<b.i;
}

bool comp2(pct a, pct b)
{
    return a.i<b.i;
}

long long int dist(pct a, pct b)
{
    return (a.i-b.i)*(a.i-b.i)+(a.j-b.j)*(a.j-b.j);
}

void divide_et_imp(int st, int dr)
{
    int i,j;

    if(st==dr)
        return;

    int mij = (st+dr)/2;
    divide_et_imp(st,mij);
    divide_et_imp(mij+1,dr);

    vector<pct> candidati_merge;

    for(i=st;i<=dr;i++)
        if((puncte[mij].j-puncte[i].j)*(puncte[mij].j-puncte[i].j)<=dist_min)
            candidati_merge.push_back(puncte[i]);

    sort(candidati_merge.begin(),candidati_merge.end(),comp2);

    for(i=0;i<candidati_merge.size();i++)
    {
        for(j=1;i+j<candidati_merge.size();j++)
        {
            if(dist_min<dist(candidati_merge[i],candidati_merge[i+j]))
                break;
            else
                dist_min=dist(candidati_merge[i],candidati_merge[i+j]);
        }
    }



}


int main()
{
    int n,m,i,j,k,t,q,nr,minim,maxim,suma;
    pct model;
    fin>>n;
    for(i=0;i<n;i++)
    {
        fin>>model.j>>model.i;
        puncte.push_back(model);
    }
    sort(puncte.begin(),puncte.end(),comp);
    divide_et_imp(0,n-1);
    fout<<fixed<<setprecision(11)<<sqrtl(dist_min)<<'\n';


    return 0;
}