Cod sursa(job #3178751)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 2 decembrie 2023 13:14:18
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#define sz 100005
long long INF = LLONG_MAX;
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

int n;


struct poz{
long long x;
long long y;};

poz v[sz + 5];

long long dist(poz a,poz b)
{
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}


long long divide_imp(int st,int dr)
{
    if(dr-st+1<=3)
    {
        long long md = INF;
        for(int i = st;i<dr;i++)
            for(int j = i + 1;j<=dr;j++)
                if(dist(v[i],v[j]) < md)
                    md = dist(v[i],v[j]);
        return md;
    }
    int mid = (st+dr)/2;
    long long d = min(divide_imp(st,mid),divide_imp(mid+1,dr));
    poz aux[dr-st+2];
    int k = 0;
    for(int i = st; i<=dr ; i++)
        if( (v[i].x - v[mid].x)*(v[i].x-v[mid].x) < d)
            aux[++k] = v[i];
    sort(aux + 1,aux + k + 1,[](poz a,poz b){return a.y<b.y;});
    for(int i = 1;i<=k;i++)
        for(int j = i+1;j<=k && (aux[i].y-aux[j].y)*(aux[i].y-aux[j].y) < d;j++)
            d=min(d,dist(aux[i],aux[j]));
    return d;
}


int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,[](poz a,poz b){return a.x<b.x;});
    long long sol = divide_imp(1,n);
    fout<<fixed<<setprecision(6)<<sqrt(sol);
}