Cod sursa(job #2501024)

Utilizator MihneaGhiraMihnea MihneaGhira Data 28 noiembrie 2019 23:05:01
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
long long n;
pair <long long,long long> v[100001],a[100001],b[100001];

long long dist(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);
}

long long interclasare(long long st,long long mid,long long dr){
    long long i=st;
    long long j=mid+1;
    long long k=st-1;
    while(i<=mid&&j<=dr){
        if(v[i].y<v[j].y)
            a[++k]=v[i++];
        else
            a[++k]=v[j++];
    }
    for(;i<=mid;i++)
        a[++k]=v[i];
    for(;j<=dr;j++)
        a[++k]=v[j];
    for(i=st;i<=dr;i++)
        v[i]=a[i];
}

long long divide(long long st,long long dr){
    long long sol,i,j,d,d1,d2,nr=0;
    if(dr-st==1){
        d=dist(v[st],v[dr]);
        interclasare(st,st,dr);
        return d;
    }
    if(dr-st==2){
        d=min(dist(v[st],v[dr]),min(dist(v[st+1],v[st]),dist(v[st+1],v[dr])));
        interclasare(st,st,dr-1);
        interclasare(st,dr-1,dr);
        return d;
    }
    long long mid=(st+dr)/2;
    d1=divide(st,mid);
    d2=divide(mid+1,dr);
    sol=min(d1,d2);
    for(i=st;i<=dr;i++){
        if(abs(v[mid].x-v[i].x)<=sol){
            b[++nr]=v[i];
        }
    }
    for(i=1;i<nr;i++)
        for(j=i+1;j<=min(nr,i+7);j++)
            sol=min(sol,dist(b[i],b[j]));
    return sol;
}

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(7)<<fixed<<(double)sqrt(divide(1,n));

    return 0;
}