Cod sursa(job #2768928)

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