Cod sursa(job #1463179)

Utilizator george_stelianChichirim George george_stelian Data 20 iulie 2015 14:10:57
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define x first
#define y second

using namespace std;

typedef long long ll;
const ll inf=2e62;
pair<int,int> v[100010],v1[100010],aux[100010];

ll dist(pair<int,int> a,pair<int,int> b)
{
    return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
}

int cmp(pair<int,int> a,pair<int,int> b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}

ll solve(int st,int dr)
{
    if(st>=dr) return inf;
    else if(st+1==dr)
    {
        if(cmp(v1[dr],v1[st])) swap(v1[st],v1[dr]);
        return dist(v[st],v[dr]);
    }
    int mid=(st+dr)/2,nr=0;
    ll sol=min(solve(st,mid),solve(mid+1,dr));
    merge(v1+st,v1+mid+1,v1+mid+1,v1+dr+1,aux+1,cmp);
    copy(aux+1,aux+2+dr-st,v1+st);
    for(int i=1;i<=dr-st+1;i++)
        if(abs(aux[i].x-v[mid].x)<=sol) aux[++nr]=aux[i];
    for(int i=1;i<=nr;i++)
        for(int j=i+1;j<=nr && j-i<=7;j++) sol=min(sol,dist(aux[i],aux[j]));
    return sol;
}

int main()
{
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i].x,&v[i].y);
    sort(v+1,v+1+n);
    for(int i=1;i<=n;i++) v1[i]=v[i];
    printf("%f",sqrt(solve(1,n)));
    return 0;
}