Cod sursa(job #3368504)

Utilizator IleaIlea Bogdan Ilea Data 14 octombrie 2026 21:55:27
Problema Cele mai apropiate puncte din plan Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define NMAX 100001
#define INF 0x7fffffff

typedef struct Point{
	int x,y;
}Point;

Point X[NMAX],Y[NMAX],tmp[NMAX];

long long sqDist(Point A,Point B){
	return (long long)(A.x-B.x)*(long long)(A.x-B.x)+(long long)(A.y-B.y)*(long long)(A.y-B.y);
}
void swap(Point*p1,Point*p2){
	Point p3=*p2;
	*p2=*p1;
	*p1=p3;
}

int comp_Point(const void*a,const void*b){
	Point pa=*(Point*)a;
	Point pb=*(Point*)b;

	if(pa.x<pb.x)return -1;
	if(pa.x>pb.x)return 1;
	if(pa.y<pb.x)return -1;
	if(pa.y>pb.y)return -1;
	return 0;
}

bool cmp(Point p1,Point p2){
	if(p1.x>p2.x)return true;
	if(p1.x==p2.x&&p1.y>p2.y)return true;
	return false;
}

long long min(long long x,long long y){
	return x<y ? x : y;
}

void merge_sort(int st,int dr){
	//printf("p5: %d %d\n",st,dr);
	if(dr-st<=1)return;
	int mij=(st+dr)/2;
	merge_sort(st,mij);
	merge_sort(mij,dr);
	int i1=st,i2=mij,i=st;
	while(i1<mij&&i2<dr){
		if(cmp(Y[i1],Y[i2])){
			tmp[i]=Y[i2];
			++i;
			++i2;
		}else{
			tmp[i]=Y[i1];
			++i;
			++i1;
		}
	}
	while(i1<mij){
		tmp[i]=Y[i1];
		++i;
		++i1;
	}
	while(i2<dr){
		tmp[i]=Y[i2];
		++i;
		++i2;
	}
}
void copy(int st,int dr){
	for(int i=st;i<dr;++i){
		//printf("%d\n",i);
		Y[i]=tmp[i];
	}
}

long long solve(int st,int dr){
	//printf("p1: %d %d\n",st,dr);
	if(dr-1<=st){
		//printf("p2: %d %d\n",st,dr);
		return INF;
	}else if(dr-st==2){
		if(cmp(Y[st],Y[st+1])){
			swap(&Y[st],&Y[st+1]);
		}
		return sqDist(X[st],X[st+1]);
	}
	//printf("p3: %d %d\n",st,dr);
	int mij=(st+dr)/2;
	long long d=min(solve(st,mij),solve(mij,dr));
	
	//printf("p4: am ajuns aici %d\n",mij);	
	merge_sort(st,dr);
	copy(st,dr);

	int tmp_size=0;
	for(int i=st;i<dr;++i){
		if(abs(Y[i].y-X[mij].x)<=d){
			tmp[tmp_size]=Y[i];
			++tmp_size;
		}
	}
	// printf("%d",tmp_size);
	for(int i=0;i<tmp_size-1;++i){
		for(int j=i+1;j<tmp_size&&j-i<8;++j){
			d=min(d,sqDist(tmp[i],tmp[j]));
		}
	}
	return d;
}

int main(){
	FILE*f=fopen("cmap.in","r");
	FILE*r=fopen("cmap.out","w");
	int n;
	fscanf(f,"%d",&n);
	for(int i=0;i<n;++i){
		fscanf(f,"%d %d",&X[i].x,&X[i].y);
		Y[i].x=X[i].y;
		Y[i].y=X[i].x;
	}
	qsort(X,n,sizeof(X[0]),comp_Point);
	// printf("%lld\n",solve(0,n));
	fprintf(r,"%0.6Lf",sqrtl(solve(0,n)));
	fclose(r);
	fclose(f);
	return 0;
}