学步园

/*
通过这题对分治、递归均有了更深一层的理解。
花在理解和coding上的时间值得了 */

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

typedef struct Node
{
	double x, y;	
}Node;

Node array[100010];
Node a[100010];
const int inff = 65535;

bool cmpx(Node a, Node b)
{
	return a.x < b.x;
}

bool cmpy(Node a, Node b)
{
	return a.y < b.y;
}

double Euc(Node a, Node b)
{
	return sqrt( (a.x - b.x) * (a.x- b.x) + (a.y - b.y) * (a.y - b.y));
}

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

double minDist(int lower, int upper)
{
	//base情况：1点、2点、3点间的最小距离都可以直接求出 
	if(lower == upper)
	{
		return inff;
	}
	if(lower + 1 == upper)
	{
		return Euc(array[lower], array[upper]);
	}
	if(lower + 2 == upper)
	{
		return min( Euc(array[lower], array[lower + 1]), min( Euc(array[lower], array[upper]), Euc(array[lower + 1], array[upper]) ) );
	}
	
	//normal情况：递归求取最小距离   分两种情况：1、minDist来自左边或者右边
	//											 2、minDist点对分跨左右 
	int midX = (lower + upper) >> 1;		 //X中心点划分 
	double lMin = minDist(lower, midX);      //左 
	double rMin = minDist(midX+1, upper);	 //右 
	double delta = min(lMin, rMin);			 
	int i,t = 0;
	//memset(a, 0, sizeof(a));
	for(i = lower; i <= upper; ++i)          //filter，如果 x-midX 都大于delta了，就不用考虑 
	{
		if(array[i].x >= array[midX].x - delta && array[i].x <= array[midX].x + delta)
		{
			a[t++] = array[i];
		}
	}
	
	sort(a, a+t, cmpy);
	
	double tmpDelta;
	
	for(i = 0; i < t - 1; ++i)
	{
		int flag = 0;
		for(int j = i + 1; j < t; ++j, ++flag)   
		{
			if(flag > 7)				//优化：由鸽笼定理，对于任取的左点p，最多不超过7个右点满足 dist(p, q) <= delta 
				break;					//理解这个花了比较久的时间 
			tmpDelta = Euc(a[i], a[j]);
			if(tmpDelta < delta)
				delta = tmpDelta;
		}
	}
	
	return delta;
}



int main(void)
{	
	//freopen("1.txt", "r", stdin);
	int N;
	double re;
	while(cin >> N, N)
	{
		int i = 0;
		while(N--)
		{
			cin >> array[i].x >> array[i].y;
			i++;
		}
		
		sort(array, array + i, cmpx);
		re = minDist(0, i - 1) / 2;
		printf("%.2f\n", re);
		//cout << minDist(0, i - 1) / 2 << endl;
		//memset(array, 0, sizeof(array));
	}

	return 0;
}