Cod sursa(job #1201261)

Utilizator RathebaSerbanescu Andrei Victor Ratheba Data 24 iunie 2014 18:28:02
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
#define MAX 100005
const long long INF=1ll<<62;
struct punct
{
    int x, y;
}v[MAX];
bool cmp(punct a, punct b){return a.x < b.x;}
int y[MAX], aux[MAX];
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 i, n;
    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("%f",sqrt((double)solve(1,n)));
    return 0;
}
long long solve(int st, int dr)
{
    int mij, k, i, j;
    long long d, ds, dd;
    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 = (st+dr)/2;
    d=solve(st, mij);
    dd=solve(mij+1,dr);
    if(d > dd) d = dd;
    k=0;
    while(i<=mij and j<=dr)
    {
        if(v[y[i]].y < v[y[i]].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];
    k=0;
    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(d>dd) d = dd;
        }
    return d;

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