Cod sursa(job #700709)

Utilizator sefubanilorSefu Banilor sefubanilor Data 1 martie 2012 11:39:44
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>

#define I64 long long
#define maxN 100005
#define INF 1LL << 61

using namespace std;


FILE*f=fopen("cmap.in","r");
FILE*g=fopen("cmap.out","w");

int n,i; double Dmin;

struct pct{
	int x;
	int y;
}a[maxN],b[maxN],vaux[maxN];

struct cmp{
	inline bool operator() ( const pct &a, const pct &b ){
		if ( a.x != b.x )
			return a.x < b.x;
		return a.y < b.y;
	}
};

inline I64 dist( pct a, pct b ){
	I64 aux = 1LL*(a.x - b.x) * (a.x - b.x) + 1LL*(a.y - b.y) * (a.y - b.y);
	return aux;
}

inline I64 abs( I64 j ){
	if ( j < 0 )
		return -j;
	return j;
}

inline void swap( int u , int v ){
	pct aux = a[u];
	a[u] = a[v];
	a[v] = aux;
}

inline I64 Min ( I64 a , I64 b ){
	if ( a < b )
		return a;
	return b;
}

inline void read () {
	fscanf(f,"%d",&n);
	
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&a[i].x,&a[i].y);
	}
	
	sort(a+1,a+n+1,cmp());
	
	for ( i = 1; i <= n ; ++i )	b[i] = a[i];
}

inline void merge ( int st, int dr , int mj ){
	
	int i,i1,i2,nr = 0;
	
	for ( i1 = st , i2 = mj + 1 ; i1 <= mj && i2 <= dr ; ){
		if ( a[i1].y < a[i2].y ){
			vaux[++nr] = a[i1++];
		}
		else{
			vaux[++nr] = a[i2++]; 
		}
	}
	for ( ; i1 <= mj ; ++i1 )
		vaux[++nr] = a[i1];
	for ( ; i2 <= dr ; ++i2 )
		vaux[++nr] = a[i2];
	
	for ( i = st , nr = 0 ; i <= dr ; ++i ){
		a[i] = vaux[++nr];
	}
	
}

I64 Div( int st , int dr ){
	if ( st >= dr )	return INF;
	I64 S; 
	if ( !(dr - st -1) ){
		if ( a[st].y > a[dr].y ){ 
			swap(st,dr);
		}
		S = dist(a[st],a[dr]);
		return S;
	}
	int mj = ( st + dr ) >> 1;
	
	S = Min(Div(st,mj) , Div(mj+1,dr));
	
	merge(st,dr,mj);
	
	int i , j , nr = 0;
	
	for ( i = st ; i <= dr ; ++i ){
		if ( abs( a[i].x - b[mj].x ) ){
			vaux[++nr] = a[i];
		}
	}
	
	for ( i = 1 ; i <= nr ; ++i ){
		for ( j = 1 ; j <= 7 ; ++j ){
			if ( i + j <= nr ){
				S = Min(S,dist(vaux[i],vaux[i+j])); 
			}
		}
	}
	
	return S;
	
}

int main () {
	
	read();
	
	Dmin = sqrt(Div(1,n));
	
	fprintf(g,"%lf\n",Dmin);
	
	fclose(f);
	fclose(g);
	
	return 0;
}