Cod sursa(job #1305018)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 29 decembrie 2014 14:47:04
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define Nmax 100005
#define INF (1LL<<61)

using namespace std;

pair < long long, long long > x[Nmax],y[Nmax],Aux[Nmax];
int n;

inline 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);
}

inline long long Solve(int l, int r)
{
    if(l>=r) return INF;
    if(r-l==1)
    {
        if(y[l]>y[l+1]) swap(y[l],y[l+1]);
        return Dist(x[l],x[l+1]);
    }
    int mid=((l+r)>>1),len=0,i,j;
    long long d;
    d=min(Solve(l,mid),Solve(mid+1,r));
    merge(y+l,y+mid+1,y+mid+1,y+r+1,Aux+1);
    copy(Aux+1,Aux+(r-l+2),y+l);
    for(i=l;i<=r;++i)
        if(abs(x[mid].first-y[i].second)<=d) Aux[++len]=y[i];
    for(i=1;i<len;++i)
        for(j=i+1;j<=len && j<=i+5;++j)
            d=min(d,Dist(Aux[i],Aux[j]));
    return d;
}

int main()
{
    int i;
    freopen ("cmap.in","r",stdin);
    freopen ("cmap.out","w",stdout);
    scanf("%d", &n);
    for(i=1;i<=n;++i) scanf("%lld%lld", &x[i].first,&x[i].second);
    sort(x+1,x+n+1);
    for(i=1;i<=n;++i) y[i]=make_pair(x[i].second,x[i].first);
    printf("%.10lf\n", sqrt(1.0*Solve(1,n)));
    return 0;
}