Cod sursa(job #1201142)

Utilizator RathebaSerbanescu Andrei Victor Ratheba Data 24 iunie 2014 15:39:38
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
#define MAX 100005
const long long INF = 1ll<<62;
struct punct
{
    int x, y;
}v[MAX];
int y[MAX], aux[MAX];
bool cmp(punct a, punct b) {return a.x < b.x;}
long long solve(int st, int dr);
long long dist(punct a, punct b);
int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    int n, i;
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        scanf("%d%d",&v[i].x,&v[i].y);
        y[i]=i;
    }
    sort(v+1, v+n+1, cmp);
    printf("%lf\n",sqrt((double)solve(1,n)));
    return 0;
}
long long solve(int st, int dr)
{
    int mij, i, j, k;
    long long ds, dd, d;
    if(st+1 == dr)
    {
        if(v[st].y > v[dr].y)
        {
            y[st]=dr; y[dr]=st;
        }
        return dist(v[st],v[dr]);
    }
    if(st==dr) return INF;
    mij = (dr+st)/2;
    d = solve(st, mij);
    dd = solve(mij+1, dr);
    if(d > dd) d=dd;
    i=st; j=mij+1;
    k=0;
    while(i <= mij and j <= dr)
    {
        if(v[y[i]].y <= v[y[j]].y)
            aux[++k] = y[i++];
        else
            aux[++k] = y[j++];
    }
    while(i<=mij) aux[++k] = y[i++];
    while(j<=dr) aux[++k] = y[j++];
    for(i=st; i<=dr; i++)
        y[i] = aux[i-st+1];
    for(i=st; i<=dr; i++)
        if(abs(v[mij].x-v[y[i]].x) <= d)
            aux[++k] = y[i];
    for(i=1; i<k; i++)
        for(j=1; j<8 && i+j<=k; j++)
        {
            dd = dist(v[aux[i]], v[aux[i+j]]);
            if(!dd) dd=INF;
            if(d>dd) d = dd;
        }
    return d;

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