Cod sursa(job #3294284)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 20 aprilie 2025 23:29:48
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <bits/stdc++.h>
#define VMAX 100005
#define INF 2000000000
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 || a.i==b.i && a.j<b.j;
}

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(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-st)/2;
    divide_et_imp(st,mij);
    divide_et_imp(mij+1,dr);
    vector<pct> interclasat;

    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=st;j<=dr;i++)
        puncte[i]=interclasat[i-st];

    for(i=st;i<=dr;i++)
    {
        for(j=1;j<=8 && i+j<=dr;j++)
            dist_min=min(dist_min,dist(puncte[i],puncte[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);
    }
    divide_et_imp(0,n-1);
    fout<<fixed<<setprecision(11)<<sqrtl(dist_min)<<'\n';


    return 0;
}