找最近对的分治法 C语言实现

找最近对的分治法 C语言实现 时间复杂度是NlogN 分治法

#include 
#include 
#include 

#define    MAXLEN	200


int init（float *xfloat *yint *ind）
{
	int ni;
	while（1==scanf（“%d“&n））
	{
		if（n > 1） break;
		printf（“n invalid!\n“）;
	}

	for（i=0;i	{
		scanf（“%f%f“x+iy+i）;
		ind[i]=i;
	}

	return n;
}

void pre_sort（float *xfloat *yint *indint n）
{//must finish in O（nlogn） but here using normorl sort method
	//bubble sort
	int ij;
	int tmp;
	float tmp_ytmp_x;

	for（i=0;i		for（j=n-1;j > i;j--）
			if（x[j-1] > x[j]）
			{
				//swap x
				tmp_x=x[j-1];
				x[j-1]=x[j];
				x[j]=tmp_x;
				//swap y
				tmp_y=y[j-1];
				y[j-1]=y[j];
				y[j]=tmp_y;
				//swap ind no need now!
				/*tmp=ind[j-1];
				ind[j-1]=ind[j];
				ind[j]=tmp;*/
			}
	for（i=0;i		for（j=n-1;j > i;j--）
			if（y[j-1] > y[j]）
			{
				//swap y
				tmp_y=y[j-1];
				y[j-1]=y[j];
				y[j]=tmp_y;
				//swap ind
				tmp=ind[j-1];
				ind[j-1]=ind[j];
				ind[j]=tmp;
			}
}

float get_pair_len（float x1float y1float x2float y2）
{
	return sqrt（（x2-x1）*（x2-x1）+（y2-y1）*（y2-y1））;
}

void find_closest_pair（int stint edfloat *xfloat *yint *indfloat *closestfloat *x1float *y1float *x2float *y2）
{//key code
	if（ed-st == 1）{//only 2 point
		*closest=get_pair_len（x[ind[0]]y[0]x[ind[1]]y[1]）;
		*x1=x[ind[0]];
		*y1=y[0];
		*x2=x[ind[1]];
		*y2=y[1];
	}
	else if（ed-st ==2）
	{//only 3 point
		float len;
		*closest=get_pair_len（x[ind[0]]y[0]x[ind[1]]y[1]）;
		*x1=x[ind[0]];
		*y1=y[0];
		*x2=x[ind[1]];
		*y2=y[1];

		len=get_pair_len（x[ind[0]]y[0]x[ind[2]]y[2]）;
		if（len < *closest）{
			*closest=len;
			*x1=x[ind[0]];
			*y1=y[0];
			*x2=x[ind[2]];
			*y2=y[2];
		}

		len=get_pair_len（x[ind[1]]y[1]x[ind[2]]y[2]）;
		if（len < *closest）{
			*closest=len;
			*x1=x[ind[1]];
			*y1=y[1];
			*x2=x[ind[2]];
			*y2=y[2];
		}
	}else{//at least 4 points
		int iclcrct;
		int mid;
		float t_c1t_c2;
		float t_c1_x1t_c1_y1t_c1_x2t_c1_y2;
		float t_c2_x1t_c2_y1t_c2_x2t_c2_y2;
		float *yl*yr*yct;
		int *indl*indr*indct;

		mid=（st+ed）/2;
		yl=（float*）malloc（（mid-st+1）*sizeof（float））;
		indl=（int*）malloc（（mid-st+1）*sizeof（int））;
		yr=（float*）malloc（（ed-mid）*sizeof（float））;
		indr=（int*）malloc（（ed-mid）*sizeof（int））;

		if（!yl || !yr || !indl || !indr） exit（-2）;//non enough mm

		for（i=0cl=0cr=0;i<=ed-st;i++）
		{//store new order y&ind
			if（ind[i] <= mid）{
				yl[cl]=y[i];
				indl[cl]=ind[i];
				cl++;
			}
			else{
				yr[cr]=y[i];
				indr[cr]=ind[i];
				cr++;
			}
		}

		//divided
		find_closest_pair（stmidxylindl&t_c1&t_c1_x1&t_c1_y1&t_c1_x2&t_c1_y2）;
		find_closest_pair（mid+1edxyrindr&t_c2&t_c2_x1&t_c2_y1&t_c2_x2&t_c2_y2）;

		if（t_c1 < t_c2）{
			*closest=t_c1;
			*x1=t_c1_x1;
			*y1=t_c1_y1;
			*x2=t_c1_x2;
			*y2=t_c1_y2;
		}
		else{
			*closest=t_c2;
			*x1=t_c2_x1;
			*y1=t_c2_y1;
			*x2=t_c2_x2;
			*y2=t_c2_

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4270  2011-09-15 14:25  find_closet_pair\find_closest_pair.cpp

     文件       4405  2011-09-13 21:57  find_closet_pair\find_closet_pair.dsp

     文件        555  2011-09-13 21:42  find_closet_pair\find_closet_pair.dsw

     文件      41984  2011-09-15 14:28  find_closet_pair\find_closet_pair.ncb

     文件      48640  2011-09-15 14:28  find_closet_pair\find_closet_pair.opt

     文件       1636  2011-09-15 14:25  find_closet_pair\find_closet_pair.plg

     目录          0  2011-09-16 13:02  find_closet_pair\Debug

     目录          0  2011-09-15 14:28  find_closet_pair

----------- ---------  ---------- -----  ----

               101490                    8