Cod sursa(job #3294287)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 21 aprilie 2025 00:06:05
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.52 kb
#include <bits/stdc++.h>
#define VMAX 100005
#define INF 200000000000000000
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");

struct pct{
long double i,j;
};
vector<pct> puncte;
long double 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 || a.i==b.i && a.j<b.j;
}

long double 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(dr-st<=2)
    {
        for(i=st;i<=dr;i++)
        {
            for(j=i+1;j<=dr;j++)
                dist_min=min(dist_min,dist(puncte[i],puncte[j]));
        }
        if(dr-st==1) // 2 numere
        {
            if(!comp2(puncte[st],puncte[dr]))
                swap(puncte[st],puncte[dr]);
        }
        else if(dr-st==2)
        {
            if(!comp2(puncte[st],puncte[dr-1]))
                swap(puncte[st],puncte[dr-1]);
            if(!comp2(puncte[dr-1],puncte[dr]))
                swap(puncte[dr-1],puncte[dr]);
            if(!comp2(puncte[st],puncte[dr-1]))
                swap(puncte[st],puncte[dr-1]);
        }
        return;
    }

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

    vector<pct> interclasat;
    vector<pct> candidati_merge;

    for(i=st,j=mij+1;i<=mij && j<=dr;)
    {
        if(comp2(puncte[i],puncte[j]))
            interclasat.push_back(puncte[i++]);
        else
            interclasat.push_back(puncte[j++]);
    }

    for(;i<=mij;i++)
    {
        interclasat.push_back(puncte[i]);
    }

    for(;j<=dr;j++)
    {
        interclasat.push_back(puncte[j]);
    }

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

    for(i=st;j<=dr;i++)
    {
        puncte[i]=interclasat[i-st];
    }


    for(i=0;i<candidati_merge.size();i++)
    {
        for(j=1;j<=8 && i+j<candidati_merge.size();j++)
            dist_min=min(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;
}