Cod sursa(job #432443)

Utilizator hasegandaniHasegan Daniel hasegandani Data 2 aprilie 2010 13:06:51
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.86 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>

using namespace std;

#define Nmax 5010
#define NNlog 60010
#define inf 0x3f3f3f3f

struct copac
{
    int x,y;
} v[Nmax];

int n,M[Nmax];
int Dx[NNlog],Dy[NNlog],K,D[NNlog];

int dist(int i,int j)
{
    return ( (v[i].x-v[j].x)*(v[i].x-v[j].x) + (v[i].y-v[j].y)*(v[i].y-v[j].y) );
}

int cmpY(copac i,copac j)
{
    return (i.y < j.y);
}

int caut(int st,int dr,double Y)
{
    int last=dr+1,mid;

    while( st<=dr )
        {
        mid = st + (dr-st)/2;
        if (Y <= (double)v[mid].y)
            {
            dr=mid-1;
            last=mid;
            }
        else
            st=mid+1;
        }
    return last;
}

int gaseste(int in,int sf,int in2,int sf2,int MAX)
{
    int dif,poz=0,prim;
    double Y;
    sort(v+in2,v+sf2+1,cmpY);

    for(int i=sf;i>=in;--i)
        {
        dif = (M[in2] - v[i].x)*(M[in2] - v[i].x);
        if (dif <= MAX)
            {
            Y= sqrt(MAX-dif);
            prim= caut(in2,sf2,max( (double)v[in2].y , v[i].y - Y));
            for(int j=prim ; (double)v[j].y <= (double)v[i].y + Y && j<=sf2 ;++j)
                if (MAX > dist(i,j))
                    {
                    MAX = dist(i,j);
                    poz = i;
                    }
            }
        }
    if (!poz)
        poz=in;
    D[++K]=MAX;
    Dx[K]=v[poz].x;
    Dy[K]=v[poz].y;
    return K;
}

int divide(int st,int dr)
{
    if (dr-st==1)  // 2 elem
        {
        D[++K]=dist(st,dr);
        Dx[K]=v[st].x;
        Dy[K]=v[st].y;
        return K;
        }
    if (dr-st==2) // 3 elem
        {
        D[++K]=dist(st,dr);
        Dx[K]=v[st].x;
        Dy[K]=v[st].y;
        if (D[K] > dist(st,dr-1))
            D[K] = dist(st,dr-1);
        if (D[K] > dist(st+1,dr))
            {
            D[K] = dist(st+1,dr);
            Dx[K]=v[st+1].x;
            Dy[K]=v[st+1].y;
            }
        return K;
        }
    int mid=st+(dr-st)/2;
    int poz1=divide(st,mid);
    int poz2=divide(mid+1,dr);
    int d=min(D[poz1],D[poz2]);
    int poz3=gaseste(st,mid,mid+1,dr,d);
    d=min(d,D[poz3]);

    if (d==D[poz1])
        return poz1;
    if (d==D[poz2])
        return poz2;
    if (d==D[poz3])
        return poz3;
    return 0;
}

bool cmp(copac i,copac j)
{
    if (i.x == j.x)
        return (i.y < j.y);
    return (i.x < j.x);
}

void solve()
{
    sort(v+1,v+n+1,cmp);
    for(int i=1;i<=n;++i)
        M[i]=v[i].x;

    int poz;
    poz=divide(1,n);

    double Solutie = sqrt(D[poz]);
    printf("%.6lf\n",Solutie);
}

void cit();

int main()
{
    cit();
    solve();
    return 0;
}

void cit()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&v[i].x,&v[i].y);
}