Cod sursa(job #1008072)

Utilizator lucky1992Ion Ion lucky1992 Data 10 octombrie 2013 10:11:28
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cstdio>

using namespace std;
  
  
#define x first
#define y second


typedef long long llong; 
typedef pair<llong,llong> Pair;
 
const int Nmax = 100010;
const llong oo = 1LL << 60;
int N;
Pair A[Nmax], B[Nmax],V[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;
	
}
llong square( llong a ){
	return a*a;
}

llong  distance1( Pair& a, Pair& b ){

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



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

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

llong go( int left, int right ){

	if( right - left < 2 ){
		llong min1 = distance1( A[left], A[left+1] );
		for( int i = left; i <= right; i++ )
			for( int j = i+1; j <= right; j++ )
				min1 = min( min1, distance1( A[i], A[j] ) );
		sort( B+left, B+right+1, cmpy );
		return min1;
	}
	
	int mid = (left+right)/2;
	
	long long delta = min( go(left, mid), go(mid+1,right) );
	
	merge( left, mid, right );
	
	int k = 1;
	
	// stripping the points
	for( int i = left; i <= right; i++ )
		if( abs( B[i].x - A[mid].x ) <= delta ){
			V[k] = B[i];
			k++;
		}
			
	
	for( int i = 1; i < k ; i++ )
		for( int j = i+1; j <= k && j-i < 8; j++ )
			delta = min(delta, distance1( V[i], V[j] ) );
	
	return delta;
	
}
		
			
int main(){

	
	ifstream in("cmap.in");
	ofstream out("cmap.out");
	in >> N;
	
	for( int i = 0; i < N; i++ ){
		in >> A[i].x >> A[i].y;
	}
	
	sort( A, A+N, cmpx );
	for( int i = 0; i < N; i++ )
		B[i] = A[i];
	
	llong rez = go( 0, N-1 );
	out<<fixed<<setprecision(6)<<sqrt(rez)<<endl;
	
	return 0;
	
}