Cod sursa(job #2508552)

Utilizator Bogdan_BuzatuBuzatu Bogdan Mihai Bogdan_Buzatu Data 12 decembrie 2019 14:46:18
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb

#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

int n;
pair<long long, long long> v[100010], aux[100010], ch[100010];

long long Distanta(pair<long long, long long>a, pair<long long, long long>b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void interclasare(int st, int mid, int dr){
    int n=mid;
    int m=dr;
    int i=st;
    int j=mid+1;
    int k=st-1;
    while(i<=n&&j<=m){
        if(v[i].y<v[j].y){
            k++;
            aux[k]=v[i];
            i++;
        }else{
            k++;
            aux[k]=v[j];
            j++;
        }

    }
    for(;i<=n;i++){
        k++;
        aux[k]=v[i];
    }

    for(;j<=m;j++){
        k++;
        aux[k]=v[j];
    }

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

    }

}
int modul(long long x,long long y){
    if(x>y){
        return x-y;
    }
    else{
        return y-x;
    }
}

long long dvd(long long st, long long dr){
    long long s;
    if(dr-st==1){
        s=Distanta(v[st], v[dr]);
        interclasare(st, st, dr);
        return s;

    }

    if(dr-st==2){
        s=min( Distanta(v[st], v[st+1]), Distanta(v[st+1], v[dr]) );
        interclasare(st, st, st+1);
        interclasare(st, st+1, dr);
        return s;

    }

    long long mid=(st+dr)/2;
    long long val1=dvd(st, mid);
    long long val2=dvd(mid+1, dr);
    interclasare(st, mid, dr);
    s=min(val1, val2);
    long long nr=0;
    for(int i=st;i<=dr;i++){
        if(modul(v[mid].x,v[mid].y) <= s){
            nr++;
            ch[nr]=v[i];
        }

    }

    for(int i=1;i<=nr;i++){
        for(int j=i+1; j<=nr && j<=i+7; j++){
            s=min(s,Distanta(ch[i],ch[j]));
        }

    }
    return s;

}



int main(){
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;

    }
    sort(v+1,v+n+1);

    fout<<setprecision(6)<<fixed<<(double)sqrt( dvd(1,n) );

}