Cod sursa(job #1472597)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 13:26:40
Problema Cele mai apropiate puncte din plan Scor 90
Compilator c Status done
Runda Arhiva educationala Marime 1.05 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef struct { long long x,y; }P;
int i,n;
P a[100001],b[100001],c[100001],d[100001];
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+1;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-1)));
}