Cod sursa(job #1389624)

Utilizator Tester100Tester Tester100 Data 16 martie 2015 14:31:54
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <iostream>
#include <algorithm>
#define fi first
#define se second
using namespace std;
const int NMAX = 100004;
pair < int ,int > v[NMAX], a[NMAX], aux[NMAX];
inline long long sqr(const long long x)
{
    return 1LL*x*x;
}
inline long long Dist(const pair < int ,int > A,const pair < int ,int > B)
{
    return sqr(A.fi-B.fi)+sqr(A.se-B.se);
}
inline long long Solve(const int Left,const int Right)
{
    if(Left >= Right)
        return 1LL<<60;
    if(Left == Right-1)
    {
        sort(a+Left,a+Right+1);
        return Dist(a[Left],a[Right]);
    }
    int mid = (Left+Right)/2;
    long long Sol = min(Solve(Left,mid),Solve(mid+1,Right));
    merge(a+Left,a+mid+1,a+mid+1,a+Right+1,aux);
    copy(aux,aux+Right-Left+1,a+Left);
    int k = 0;
    for(int i=Left;i<=Right;++i)
        if(sqr(a[i].se-v[mid].fi) <= Sol)
            aux[++k] = a[i];
    for(int i = 1;i <= k;++i)
        for(int j=i+1;j <= k && j-i <= 8; ++j)
            Sol = min(Sol,Dist(aux[i],aux[j]));
    return Sol;
}

int main()
{
    int n, x, y;
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d\n",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d %d\n",&x,&y);
        v[i] = make_pair(x,y);
    }
    sort(v+1,v+n+1);
    for(int i=1;i<=n;++i)
        a[i] = make_pair(v[i].se,v[i].fi);
    long double D = sqrt(Solve(1,n));
    cout<<D<<"\n";
    return 0;
}