Cod sursa(job #2768926)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 12 august 2021 16:58:00
Problema Cele mai apropiate puncte din plan Scor 25
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include<stdio.h>
#include<math.h>
#define N 100001
#define M(a,b) ((a)<(b)?a:b)
typedef struct {
    long long x,y;
}P;
P a[N],b[N],c[N],d[N];
int i,n;
int A(const void *a,const void *b)
{
    P l=*(P*)a,r=*(P*)b;
    return l.x<r.x||(l.x==r.x&&l.y<r.y);
}
long long B(P p,P q)
{
    return (p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
}
long long D(int p,int q)
{
    if(q-p<3)
        return B(a[p],a[p+1]);
    int m=(p+q)/2,i,j,k;
    long long r=M(D(p,m),D(m,q));
    for(k=i=p,j=m+1;i<=m||j<=q;)
        if(j>q||(i<=m&&c[i].x<c[j].x))
            d[k++]=c[i++];
        else
            d[k++]=c[j++];
    for(j=0,i=p;i<=q-p+1;++i)
        if(abs(d[i].y-a[m].x)<=r)
            b[++j]=d[i];
    for(i=1;i<j;++i)
        for(k=i+1;k<=j&&k-i<8;++k)
            r=M(r,B(b[i],b[k]));
    return r;
}
int main()
{
    freopen("cmap.in","r",stdin),freopen("cmap.out","w",stdout),scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%lld%lld",&a[i].x,&a[i].y);
    qsort((void*)(a+1),n,sizeof(a[1]),A);
    for(i=1;i<=n;++i)
        c[i].x=a[i].y,c[i].y=a[i].x;
    printf("%.6lf\n",sqrt(D(1,n)));
}