华中科技大学2018算法实验

华中科技大学2018算法实验 。

#include 
#include 
#include  
#include  
#include
using namespace std;

const double infinite = 0x1ffffff;
int minPointNum = 0; //统计有多少个最短点
int  PointNumber;
class Point {
public:
	Point（） {	}
	Point（double x double y）
	{
		Point::x = x;
		Point::y = y;
	}
	int x;
	int y;
} ;  //直接建立点集

int *strip_area;
Point *po;
struct minPoints {
	double cal;
	int left;
	int right;
}; //最小距离点的点集
minPoints *minP;


/*比较x坐标的大小*/
/*若a小于b就返回1*/
int cmp_x（Point a Point b）
{
	return a.x < b.x;
}

/*比较y坐标的大小*/
int cmp_y（int a int b）
{
	return po[a].y < po[b].y;
}


/*计算两点间的最短距离*/
double cal_point_distance（Point a Point b）
{
	return sqrt（（a.x - b.x）*（a.x - b.x） + （a.y - b.y）*（a.y - b.y））;
}

/*分而治之地计算最短距离*/
/*n为点的个数，list为点集*/
double cal_min_distance（const int left const int right）
{
	double min = infinite;
	//如果只有一个点，那么最短距离就是无穷大
	if （left == right） return infinite;

	//如果有两个点，那么最短距离就是两者间的距离
	if （right == left + 1）
	{
		int point_distance = cal_point_distance（po[left] po[right]）;

		if （minP[minPointNum].cal == point_distance） {
			if （!（（minP[minPointNum].left == left） && （minP[minPointNum].right == right）））
			{
				//两个点的左右不能完全相等
				//如果存在相同的最小距离，那么最短距离点的个数就会加
				minPointNum++;
				minP[minPointNum].cal = point_distance;
				minP[minPointNum].left = left;
				minP[minPointNum].right = right;
			}
		}
		else if （point_distance < minP[minPointNum].cal）
		{
			//如果距离要大于算出来的距离，那么让相同最短距离点个数回到0（代表1）
			minPointNum = 0;
			minP[minPointNum].cal = point_distance;
			minP[minPointNum].left = left;
			minP[minPointNum].right = right;
		}
		return point_distance;
	}

	int middle = （left + right） / 2;

	double left_dis = cal_min_distance（left middle）;
	double right_dis = cal_min_distance（middle + 1 right）;

	min = left_dis < right_dis ? left_dis : right_dis;

	/*下面确定[x-minx+min]的区域*/
	int strip_num = 0;
	for （int i = left; i <= right; i++）
	{
		if （fabs（po[middle].x - po[i].x） <= min）
			strip_area[strip_num++] = i;
	}

	//按纵坐标升序排列这些点
	sort（strip_area strip_area + strip_num cmp_y）;


	for （int i = 0; i < strip_num; i++）
	{
		int k = （（i + 7） > strip_num） ? strip_num : （i + 7）; //最多只用算7次
		double strip_min;
		for （int j = i + 1; （j < k） && （po[strip_area[j]].y - po[strip_area[i]].y < min）; j++）
		{
			strip_min = cal_point_distance（po[strip_area[i]] po[strip_area[j]]）;

			if （minP[minPointNum].cal == strip_min） {

				if （strip_area[i] < strip_area[j]）
				{
					if （!（（minP[minPointNum].left == strip_area[i]） && （minP[minPointNum].right == strip_area[j]）））
					{
						minPointNum++;
						minP[minPointNum].cal = strip_min;
						minP[minPointNum].left = strip_area[i];
						minP[minPointNum].right = strip_area[j];
					}

				}
				else
				{
					if （!（（minP[minPointNum].left == strip_area[j]） && （minP[minPointNum].right == strip_area[i]）））
					{
						minPointNum++;
						minP[minPoin

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-11-14 18:06  算法实验\
     目录           0  2018-11-14 18:04  算法实验\lab1\
     文件        5159  2018-11-14 17:58  算法实验\lab1\Point_to_Point.cpp
     文件      134656  2018-11-14 17:58  算法实验\lab1\Point_to_Point.exe
     文件         119  2018-11-14 16:17  算法实验\lab1\in.dat
     文件          78  2018-11-14 18:04  算法实验\lab1\out.dat
     目录           0  2018-11-14 18:06  算法实验\lab2\
     文件      166400  2018-11-14 16:29  算法实验\lab2\BigNum.exe
     文件        6058  2018-11-14 16:29  算法实验\lab2\bignum.cpp
     文件         206  2018-11-14 18:06  算法实验\lab2\in.dat
     文件         112  2018-11-14 18:06  算法实验\lab2\out.dat
     目录           0  2018-11-14 18:07  算法实验\lab3\
     文件         818  2018-11-13 20:00  算法实验\lab3\BSTree.cpp
     文件       48640  2018-11-13 19:59  算法实验\lab3\shuanfa_lab3.exe
     目录           0  2018-11-14 13:50  算法实验\lab4\
     文件        1991  2018-11-14 13:49  算法实验\lab4\FLOYD.cpp
     文件       48111  2018-11-14 13:50  算法实验\lab4\a.exe
     文件         167  2018-11-14 13:49  算法实验\lab4\in.dat
     文件         764  2018-11-14 18:07  算法实验\lab4\out.dat