Cod sursa(job #432477)

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

using namespace std;

#define Nmax 100005
#define ll long long
const ll inf = 100000000000000000LL;

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

struct cmp
{
    inline bool operator()(pct i,pct j)
    {
        if (i.x == j.x)
            return (i.y < j.y);
        return (i.x < j.x);
    }
};
struct cmp2
{
    inline bool operator()(pct i,pct j)
    {
        return (i.y < j.y);
    }
};
int N;

double dist(pct i,pct j)
{
    return (sqrt( (i.x-j.x)*(i.x-j.x) + (i.y-j.y)*(i.y-j.y) ) );
}

double tractor(int st,int dr)
{
    double opt=inf;
    for(int i=st;i<dr;++i)
        for(int j=i+1;j<=dr;++j)
            if (opt > dist(v[i],v[j]))
                opt = dist(v[i],v[j]);
    return opt;
}

int caut(pct x,double Dmin,int M)
{
    int st=1,dr=M,last=M,mid;

    for(; st<=dr ;)
        {
        mid = st + (dr-st)/2;
        if (x.y-Dmin <= a[mid].y)
            {
            dr=mid-1;
            last = mid;
            }
        else
            st = mid+1;
        }
    return last;
}

double calc(int st,int dr)
{
    int mid,M=0;
    double d,Min;

    if (st>dr)
        return inf;
    if (dr-st < 4)
        return tractor(st,dr);

    mid = st + (dr-st)/2;
    d = min ( calc(st,mid) ,calc(mid+1,dr) );
    Min = d;
    for(int i=mid+1; v[i].x <= v[mid].x+d && i<=dr;++i)
        a[++M]=v[i];
    sort(a+1,a+M+1,cmp2());
    for(int i=st;i<=mid;++i)
        for(int j=caut(v[i],d,M); j<=M && v[i].y-d<=a[j].y && a[j].y<=v[i].y+d ;++j)
            if (Min > dist(v[i],a[j]))
                Min = dist(v[i],a[j]);
    return Min;
}

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);
}

int main()
{
    cit();
    sort(v+1,v+N+1,cmp());
    printf("%.6lf\n",calc(1,N));
    return 0;
}