Cod sursa(job #2567472)

Utilizator Ioana_GaborGabor Ioana Ioana_Gabor Data 3 martie 2020 17:28:52
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define NMAX 100000
#define x first
#define y second
#define MAXVAL (1LL<<31)-1

using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

int n;
pair <int,int> sir[NMAX+5],aux[NMAX+5];

long double dist2(int i,int j){
    return (long double)(1LL*(sir[i].x-sir[j].x)*(sir[i].x-sir[j].x)+1LL*(sir[i].y-sir[j].y)*(sir[i].y-sir[j].y));
}

long double minim(long double a,long double b){
    if(a<b){
        return a;
    }
    return b;
}

long double modul(long double a){
    if(a<0){
        return -a;
    }
    return a;
}

long double distanta(int st,int dr){
    if(dr-st+1==3){
        if(sir[dr].y<sir[st].y){
            swap(sir[st],sir[dr]);
        }
        if(sir[dr-1].y<sir[st].y){
            swap(sir[st],sir[dr-1]);
        }
        if(sir[dr].y<sir[dr-1].y){
            swap(sir[dr-1],sir[dr]);
        }
        return minim(dist2(st,st+1),minim(dist2(st+1,dr),dist2(st,dr)));
    }
    if(dr-st+1==2){
        if(sir[dr].y<sir[st].y){
            swap(sir[st],sir[dr]);
        }
        return dist2(st,dr);
    }
    int mij=(st+dr)/2,ii=st,jj=mij+1,ll=st-1,dreapta;
    long double d1,d2,dmin;
    dreapta=sir[mij].x;
    d1=distanta(st,mij);
    d2=distanta(mij+1,dr);
    dmin=minim(d1,d2);
    ///interclasare
    while(ii<=mij&&jj<=dr){
        if(sir[ii].y<sir[jj].y){
            aux[++ll]=sir[ii++];
        }else{
            aux[++ll]=sir[jj++];
        }
    }
    while(ii<=mij){
        aux[++ll]=sir[ii++];
    }
    while(jj<=dr){
        aux[++ll]=sir[jj++];
    }
    for(int i=st;i<=dr;i++){
        sir[i]=aux[i];
    }
    ll=0;
    for(int i=st;i<=dr;i++){
        if(modul(sir[i].x-dreapta)<=dmin){
            aux[++ll]=sir[i];
        }
    }
    for(int i=1;i<=ll;i++){
        for(int j=i+1;j<=min(i+7,ll);j++){
            d1=dist2(i,j);
            dmin=minim(dmin,d1);
        }
    }
    return dmin;
}

int main() {
    f>>n;
    for(int i=1;i<=n;i++){
        f>>sir[i].x>>sir[i].y;
    }
    sort(sir+1,sir+n+1);
    g<<fixed<<setprecision(6)<<sqrt((double)distanta(1,n));
}