Cod sursa(job #1423095)

Utilizator heracleRadu Muntean heracle Data 21 aprilie 2015 13:06:20
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 3.53 kb
#include <cstdio>
#include <algorithm>


FILE* in=fopen("cmap.in","r");
FILE* out=fopen("cmap.out","w");

const int SBUF=4096;
char BUF[SBUF];
int p=SBUF;

bool cif[200];

void prec()
{
    for(int i='0';i<='9'; i++)
        cif[i]=1;
}

char get_char()
{
    if(p==SBUF)
    {
        fread(BUF,SBUF,1,in);
        p=0;
    }

    return BUF[p++];
}

int get_int()
{
    char x;
    int rez=0;

    x=get_char();

    while(!cif[x])
        x=get_char();

    while(cif[x])
    {
        rez=rez*10+x-'0';
        x=get_char();
    }

    return rez;
}

const int Q=1000108,INF=2000000000;

int n;

struct point{
    long long x,y;

    void operator =(const point &alt)
    {
        x=alt.x;
        y=alt.y;
    }

} v[Q];

long long modul(long long x)
{
    return x>0?x:-x;
}

unsigned long long dist(const point &a, const point &b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

point sel[Q];

void pleaca(int st, int dr, point &a, point &b)
{
    if(st==dr)
    {
        a=v[st];
        b=v[0];
        return;
    }
    if(st==dr-1)
    {
        a=v[st];
        b=v[dr];

        if(v[dr].y<v[st].y)
        {
            point aux;

            aux=v[st];
            v[st]=v[dr];
            v[dr]=aux;
        }

        return;
    }

    int md=(st+dr)/2;

    point e,r;

    pleaca(st,md,a,b);

    pleaca(md+1,dr,e,r);

    if(dist(e,r)<dist(a,b))
    {
        a=e;
        b=r;
    }

    int x1=st,x2=md+1;

    int nr=0;

    unsigned long long eta=dist(a,b);

    while(x1<=md && x2<=dr)
    {
        if(v[x1].y<v[x2].y)
        {
            if((v[x1].x-v[md].x)*(v[x1].x-v[md].x)<=eta)
            {
                nr++;
                sel[nr]=v[x1];
            }
            x1++;
        }
        else
        {
            if((v[x2].x-v[md].x)*(v[x2].x-v[md].x)<=eta)
            {
                nr++;
                sel[nr]=v[x2];
            }
            x2++;
        }
    }
    while(x1<=md)
    {
        if((v[x1].x-v[md].x)*(v[x1].x-v[md].x)<=eta)
            {
                nr++;
                sel[nr]=v[x1];
            }
            x1++;
    }
    while(x2<=dr)
    {
         if((v[x2].x-v[md].x)*(v[x2].x-v[md].x)<=eta)
            {
                nr++;
                sel[nr]=v[x2];
            }
            x2++;
    }
    for(int i=1;i<=7;i++)
    {
        sel[nr+i]=v[0];
    }

    for(int i=1; i<=nr; i++)
    {
        for(int j=1; j<=7; j++)
        {
            if(dist(sel[i],sel[i+j])<eta)
            {
                a=sel[i];
                b=sel[i+j];
                eta=dist(sel[i],sel[i+j]);
            }
        }
    }

    nr=0;
    x1=st;
    x2=md+1;

     while(x1<=md && x2<=dr)
    {
        if(v[x1].y<v[x2].y)
        {
            nr++;
            sel[nr]=v[x1];
            x1++;
        }
        else
        {
            nr++;
            sel[nr]=v[x2];
            x2++;
        }
    }
    while(x1<=md)
    {
        nr++;
        sel[nr]=v[x1];
        x1++;
    }
    while(x2<=dr)
    {
        nr++;
        sel[nr]=v[x2];
        x2++;
    }

    for(int i=1; i<=nr; i++)
    {
        v[st+i-1]=sel[i];
    }
}

bool cmp(const point &a, const point &b)
{
    return a.x<b.x;
}

int main()
{
    prec();
    n=get_int();

    int a,b;

    for(int i=1; i<=n; i++)
    {
        a=get_int();
        b=get_int();

        v[i].x=a;
        v[i].y=b;
      //  v[i].y=1LL*b*3;
    }
    std::sort(v+1,v+n+1,cmp);

    point g,k;

    v[0].x=-INF;
    v[0].y=-INF;

    pleaca(1,n,g,k);

    unsigned long long eta=dist(g,k);

    double rez=sqrt(eta);

    fprintf(out,"%.9lf",rez);

    return 0;
}