Cod sursa(job #2380374)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 14 martie 2019 20:51:55
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

int n;
long long x,y;
vector <pair<long long,long long>> pct;
int s[100005];

long long dist(pair<long long, long long> &A, pair<long long, long long> &B){
    return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}

long long cmap(int st, int dr){
    if(dr-st+1<=3){
        long long ret = 1e15;
        for(int i=st;i<dr;++i)
            for(int j=i+1;j<=dr;++j)
                ret = min(ret, dist(pct[i],pct[j]));
        return ret;
    }
    int mij = (st+dr)>>1;
    long long ss = min(cmap(st,mij), cmap(mij+1,dr));
    int l = st, r = mij+1;
    for(int i=st;i<=dr;++i){
        if(l == mij+1 || (r<=dr && pct[l].second<=pct[r].second))
            s[i]=r++;
        else
            s[i]=l++;
    }
    for(int i=st;i<dr;++i){
        for(int j=i+1;j<=min(dr,i+7);++j)
            ss = min(ss,dist(pct[s[i]],pct[s[j]]));
    }
    return ss;
}

int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);

    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%lld%lld",&x,&y);
        pct.push_back({x,y});
    }
    sort(pct.begin(),pct.end());
    pct.push_back({0,0});

    cout<<setprecision(7)<<fixed<<sqrt(cmap(0,n-1));

    return 0;
}