Cod sursa(job #1007881)

Utilizator lucky1992Ion Ion lucky1992 Data 9 octombrie 2013 20:41:43
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
  
#define x first
#define y second
 
typedef pair<long long,long long> Pair;
 
const int Nmax = 100010;
int N;
Pair A[Nmax], B[Nmax];

bool cmpx( Pair a, Pair b ){

	if( a.x == b.x ) return a.y < b.y;
	return a.x < b.x;
	
}

bool cmpy( Pair a, Pair b ){

	if( a.y == b.y ) return a.x < b.x;
	return a.y < b.y;
	
}

long long distance( Pair a, Pair b ){

	return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
	
}

void merge( int left, int mid, int right ){

	int i = left, j = mid+1;
	int k = 0;
	Pair V[Nmax];
	
	while( i <= mid && j <= right ){
	
		if( B[i].y < B[j]. y ){
			V[k] = B[i];
			k++; i++;
		}
		else{
			V[k] = B[j];
			k++;j++;
		}
	}
	
	while( i <= mid ){
		V[k] = B[i];
		k++; i++;
	}
	
	while( j <= right ){
		V[k] = B[j];
		k++;j++;
	}
	
	int t = 0;
	for( int i = left ; t<k; t++,i++ )
		B[i] = V[t];
		
}
		

long long go( int left, int right ){

	if( left >= right )
		return 1LL<<60;
	if( right - left < 2 ){
		if( B[left].y > B[left+1].y ) 
			swap( B[left], B[left+1] );
		return distance( A[left], A[left+1] );
	}
	
	int mid = left + (right-left)/2;
	
	long long delta = min( go(left, mid), go(mid+1,right) );
	
	merge( left, mid, right );
	
	int k = 0;
	Pair V[Nmax];
	
	for( int i = left; i <= right; i++ )
		if( abs( B[i].x - A[mid].x ) <= delta )
			V[k++] = B[i];
			
	for( int i = left; i <= right; i++ )
		for( int j = i+1; j <= right && j-i < 8; j++ )
			delta = min(delta, distance( B[i], B[j] ) );
	
	return delta;
	
}
		
			
int main(){

	freopen("cmap.in", "r", stdin );
	freopen("cmap.out", "w", stdout );
	
	scanf("%d", &N );
	
	for( int i = 0; i < N; i++ )
		scanf("%lld%lld", &A[i].x, &A[i].y );
	
	sort( A, A+N, cmpx );
	for( int i = 0; i < N; i++ )
		B[i] = A[i];
	
	long long rez = go( 0, N-1 );
	
	printf("%.6lf\n", sqrt( rez ) );
	
	return 0;
	
}