Cod sursa(job #2764401)

Utilizator BalasaRaduBalasa Radu BalasaRadu Data 20 iulie 2021 19:18:12
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin ("cmap.in");
ofstream fout("cmap.out");

const int dim=100009;

struct punct{
long long x,y;}v[dim],aux[dim];

long long d=1e15;

long long dist(punct A,punct B){
    return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

bool cmp(punct A,punct B){
    if(A.x==B.x)
        return A.y<B.y;
    return A.x<B.x;
}

void dei(int st,int dr){
    if(st<dr){
        int mij=(st+dr)/2;
        long long pivot=v[mij].x;
        dei(st,mij);
        dei(mij+1,dr);

        int len=st,p1=st,p2=mij+1;
        while(p1<=mij&&p2<=dr){
            if(v[p1].y<v[p2].y)
                aux[len++]=v[p1++];
            else
                aux[len++]=v[p2++];
        }
        while(p1<=mij)
            aux[len++]=v[p1++];
        while(p2<=dr)
            aux[len++]=v[p2++];

        for(int i=st;i<=dr;i++){
            v[i]=aux[i];
        }

        len=st;
        for(int i=st;i<=dr;i++)
            if(max(pivot-v[i].x,v[i].x-pivot)<=d)
                aux[len++]=v[i];

        for(int i=st;i<len;i++){
            for(int j=max(st,i-7);j<i;j++)
                d=min(d,dist(aux[i],aux[j]));
        }
    }
}

signed main(){

    int n;
        fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp);
    dei(1,n);
        fout<<fixed<<setprecision(6)<<sqrt(d);
}