Cod sursa(job #625699)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 25 octombrie 2011 12:10:46
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>

#define PLL pair< long long, long long >
#define ll long long
#define mp make_pair
#define x first
#define y second
#define xdupay second

#define NMAX 100005
#define INF 4e18

using namespace std;

PLL X[NMAX], Y[NMAX], Aux[NMAX];
int N, i, j, lg;

inline ll Dist( const PLL &A, const PLL &B )
{
	return ( A.x - B.x )*( A.x - B.x ) + ( A.y - B.y )*( A.y - B.y );
}

inline ll Sol( int St, int Dr )
{
	if( Dr == St + 1 ) return INF;
	else if( Dr == St + 2 )
	{
		if( Y[St] > Y[Dr - 1] )
			swap( Y[St], Y[Dr - 1] );
		return Dist( X[St], X[Dr - 1] );
	}
	
	int M = (St + Dr)>>1;
	ll DistMin = min( Sol( St, M ), Sol( M, Dr ) );
	
	merge( Y + St, Y + M, Y + M, Y + Dr, Aux );
	copy( Aux, Aux + ( Dr - St ), Y + St );
	
	lg = 0;
	for( i = St; i < Dr; ++i )
		if( abs( X[M].x - Y[i].xdupay ) <= DistMin )
			Aux[ lg++ ] = Y[i];
	for( i = 0; i < lg - 1; ++i )
		for( j = i + 1; j < lg && j - i < 8; ++j )
			DistMin = min( DistMin, Dist( Aux[i], Aux[j] ) );
	
	return DistMin;
}

int main()
{
	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);
	
	ll nN = INF;
	scanf("%d", &N);
	for( i = 0; i < N; ++i )
		scanf("%lld%lld", &X[i].x, &X[i].y);
	
	sort( X, X + N );
	for( i = 0; i < N; ++i )
		Y[i] = mp( X[i].y, X[i].x );
	
	printf("%.6lf\n", sqrt((double)Sol( 0, N )) );
	
	return 0;
}