Cod sursa(job #1100941)

Utilizator andreiiiiPopa Andrei andreiiii Data 7 februarie 2014 18:02:03
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <algorithm>
#include <cstdio>
#include <cmath>
#define PLL pair<long long, long long>
#define x first
#define y second

using namespace std;

const int N=100005;
const long long INF=(1LL<<60);

PLL a[N], b[N], aux[N];

long long modul(long long k) {return (k<0?(-k):k);}

long long dist(PLL a, PLL b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

long long solve(int st, int dr)
{
    if(st>=dr) return INF;
    else if(dr==st+1)
    {
        if(b[st]>b[dr]) swap(b[st], b[dr]);
        return dist(a[st], a[dr]);
    }
    int mij=(st+dr)/2, n=0, i, j;
    long long ret=min(solve(st, mij), solve(mij+1, dr));
    merge(b+st, b+mij+1, b+mij+1, b+dr+1, aux);
    copy(aux, aux+(dr-st+1), b+st);
    for(i=st;i<=dr;i++) if(modul(b[i].x-a[mij].x)<=ret) aux[++n]=b[i];
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n&&j<i+8;j++) ret=min(ret, dist(aux[i], aux[j]));
    }
    return ret;
}

int main()
{
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    int n, i;
    long long sol;
    scanf("%d", &n);
    for(i=1;i<=n;i++) scanf("%lld%lld", &a[i].x, &a[i].y);
    sort(a+1, a+n+1);
    for(i=1;i<=n;i++) b[i]=make_pair(a[i].y, a[i].x);
    sol=solve(1, n);
    printf("%.6lf", sqrt(sol));
}