Cod sursa(job #2768930)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 12 august 2021 17:04:51
Problema Cele mai apropiate puncte din plan Scor 70
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef struct { long long x,y; }P;
int i,n;
P a[100005],b[100005],c[100005],d[100005];
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)));
}