Cod sursa(job #2969851)

Utilizator Silviu_StefanStefan Silviu Silviu_Stefan Data 23 ianuarie 2023 20:02:35
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
char buff[4096];
int pbuf=4095;
void readbuff(){
    pbuf=0;fin.read(buff,4095);
}
int citire(){
    int nr=0,semn=0;
    if(pbuf==4095){
        semn=0;readbuff();
    }
    while(buff[pbuf]<'0'||buff[pbuf]>'9'){
        if(buff[pbuf]=='-'){
            semn=1;
        }
        pbuf++;
        if(pbuf==4095){
            readbuff();
        }
    }
    while(buff[pbuf]>='0'&&buff[pbuf]<='9'){
        nr=nr*10+buff[pbuf]-'0';pbuf++;
        if(pbuf==4095){
            readbuff();
        }
    }
    if(semn==1){
        nr=-nr;
    }
    return nr;
}
int n;
struct numere{
    int x,y;
}v[100005],vst[100005],vdr[100005];
bool cmp(numere a,numere b){
    if(a.x!=b.x){
        return a.x<b.x;
    }
    else{
        return a.y<b.y;
    }
}
double dist(numere a,numere b){
    long long rez=1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
    double afis=(double)sqrt(rez);
    return afis;
}
bool cmp1(numere a,numere b){
    return a.y<b.y;
}
double F(int a,int b){
    if(b-a+1==2){
        return dist(v[a],v[b]);
    }
    if(b-a+1==3){
        return min(dist(v[a],v[a+1]),min(dist(v[a],v[b]),dist(v[a+1],v[b])));
    }
    int mij=(a+b)/2;
    double d=min(F(a,mij),F(mij+1,b));
    int lim=(int)d+1,pozst=0,pozdr=0;
    for(int i=mij;i>=a;i--){
        if(v[mij].x-v[i].x+1<=lim){
            pozst++;vst[pozst]=v[i];
        }
        else{break;}
    }
    for(int i=mij+1;i<=b;i++){
        if(v[i].x-v[mij].x+1<=lim){
            pozdr++;vdr[pozdr]=v[i];
        }
        else{break;}
    }
    sort(vst+1,vst+pozst+1,cmp1);
    sort(vdr+1,vdr+pozdr+1,cmp1);
    int pst=1,pdr=1;
    for(int i=1;i<=pozdr;i++){
        int val1=vdr[i].y-lim,val2=vdr[i].y+lim;
        while(pst<=pozst&&vst[pst].y<val1){
            pst++;
        }
        while(pdr<=pozst&&vst[pdr].y<val2){
            pdr++;
        }
        if(pst>pozst){pst--;}
        if(pdr>pozst){pdr--;}
        for(int j=pst;j<=pdr;j++){
            if(a==63166&&b==63234){
                double ceva=dist(vst[j],vdr[i]);
            }
            d=min(d,dist(vst[j],vdr[i]));
        }
    }
    return d;
}
int main()
{
    n=citire();
    for(int i=1;i<=n;i++){
        v[i].x=citire();v[i].y=citire();
    }
    sort(v+1,v+n+1,cmp);
    double distmin=F(1,n);
    long long rez=1LL*(double)distmin*100000000;
    distmin=(double)rez/100000000;
    fout<<fixed<<setprecision(6)<<distmin<<'\n';
    return 0;
}