Cod sursa(job #2768932)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 12 august 2021 17:23:18
Problema Cele mai apropiate puncte din plan Scor 20
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define M 20000000
#define N 100001
typedef struct {
    long long x,y;
}P;
P v[N],x[N],y[N],z[N],w;
int n,i,q=-1;
#define D(a,b) ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
#define Y(a,b) ((a)<(b)?a:b)
char u[M];
void T(P x[],int p,int q)
{
    if(p==q)
        return;
    int i,j,k,m=(p+q)/2;
    T(x,p,m),T(x,m+1,q);
    for(i=k=p,j=m+1;i<=m||j<=q;)
        if(j>q||(i<=m&&(x[i].x<x[j].x||(x[i].x==x[j].x&&x[i].y<x[j].y))))
            z[k++]=x[i++];
        else
            z[k++]=x[j++];
    for(i=p;i<=q;i++)
        x[i]=z[i];
}
long long A()
{
  	long long s=0,b=1;
  	q++;
  	if(u[q]==45)
        b=-1,q++;
  	for(;u[q]>47;q++)
  		s=s*10+u[q]-48;
  	return s*b;
}
long long G(int s,int d)
{
    if(d-s<2)
        return 4e18;
    if(d-s==2) {
        if(y[s].x>y[s+1].x||(y[s].x==y[s+1].x&&y[s].y>y[s+1].y))
            w=y[s],y[s]=y[s+1],y[s+1]=w;
        return D(x[s],x[s+1]);
    }
    int m=(s+d)/2,e=0,i,j;
    long long b=Y(G(s,m),G(m,d));
    for(T(y,s,d),i=s;i<d;i++)
		if(abs(y[i].y-x[m].x)<=b)
        	v[e++]=y[i];
    for(i=0;i<e-1;i++)
        for(j=i+1;j<e&&j-i<8;j++)
            b=Y(b,D(v[i],v[j]));
    return b;
}
int main()
{
	freopen("cmap.in","r",stdin),freopen("cmap.out","w",stdout),fread(u,1,M,stdin),n=A();
    for(i=0;i<n;i++)
    	x[i].x=A(),x[i].y=A();
    for(T(x,0,n-1),i=0;i<n;i++)
        y[i]=x[i];
    printf("%.6lf",sqrt(G(0,n)));
}