Cod sursa(job #1472536)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 12:19:31
Problema Cele mai apropiate puncte din plan Scor 50
Compilator c 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[100001],b[100001],c[100001],d[100001];
int A(const void *a,const void *b) {
    P *p=(P*)a,*q=(P*)b;
    return p->x<q->x||(p->x==q->x&&p->y<q->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=D(p,m)<D(m,q)?D(p,m):D(m,q);
	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>B(b[i],b[k])?B(b[i],b[k]):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)));
}