哈工大研究生算法实验

哈工大研究生算法设计与分析实验，实验内容分治算法和搜索算法

#include 
#include 
#include 
#include 
#include 

#define GEN_BOUND 100

using namespace std;

typedef struct point {
	int x;
	int y;
}POINT;

typedef struct point2 {
	int x;
	int y;
	float afa;
}POINT2;

typedef struct pointf {
	float x;
	float y;
}POINTF;

POINT* force_algorithm（POINT* Q int n）;
int line（POINT *p1 POINT* p2 POINT* k）;
bool inTriangle（POINT* a POINT* b POINT* c POINT* k）;
int compare_by_x（const void* e1 const void* e2）;
POINT* gen（int n）;



POINT* gen（int n） {
	POINT* ret = new POINT[n];
	srand（clock（））;
	for （int i = 0; i		ret[i].x = abs（rand（）） % （GEN_BOUND + 1）;
		ret[i].y = abs（rand（）） % （GEN_BOUND + 1）;
	}

	return ret;
}

bool operator == （POINT a POINT b） {
	return（a.x == b.x && a.y == b.y）;
}

//////////////////////////
POINT* force_algorithm（POINT* Q int n） {
	bool* flag = new bool[n];
	memset（flag true n）;
	for （int i = 0; i		if （!flag[i]） //若点I已被删除，则跳过
			continue;
		for （int j = i + 1; j
			if （!flag[i]）
				break;
			if （!flag[j]）
				continue;
			if （Q[i] == Q[j]） {//若I和J重叠，则删除j（==是重载运算符）
				flag[j] = false;
				continue;
			}

			for （int k = j + 1; k
				if （（!flag[i]） || （!flag[j]））
					break;
				if （!flag[k]）
					continue;

				if （Q[i] == Q[k] || Q[j] == Q[k]） {
					flag[k] = false;
					continue;
				}

				if （line（&Q[i] &Q[j] &Q[k]） == 0） {//若I J K在一条直线上，则删除中间的点
					if （Q[i].x != Q[j].x） {
						int a = Q[j].x - Q[i].x;
						int b = Q[k].x - Q[i].x;
						if （a*b<0） {
							flag[i] = false;
							break;
						}
						else {
							if （abs（a）								flag[j] = false;
								break;
							}
							else {
								flag[k] = false;
								continue;
							}
						}
					}
				}

				for （int l = 0; l					if （l == i || l == j || l == k）
						continue;
					if （!flag[l]）
						continue;

					if （inTriangle（&Q[i] &Q[j] &Q[k] &Q[l]））//若L在△IJK中，删除L
						flag[l] = false;
				}
			}
		}
	}

	POINT* R = new POINT[n];
	int j = 0;
	for （int i = 0; i		if （flag[i]） {
			R[j].x = Q[i].x;
			R[j].y = Q[i].y;
			j++;
		}
	}

	qsort（R j sizeof（POINT） compare_by_x）;//按横坐标递增的顺序排列R中的点

	POINT* S = new POINT[j + 1];
	S[j].x = S[j].y = -1;//（-1，-1）表示结尾

	int k = 0;
	for （int i = 0; i		if （line（&R[0] &R[j - 1] &R[i]） <= 0） {
			S[k].x = R[i].x;
			S[k].y = R[i].y;
			k++;
		}
	}

	for （int i = j - 1; i >= 0; i--） {//按横坐标递减顺序将R[0]R[j-1]下方的点拷贝到S中
		if （line（&R[0] &R[j - 1] &R[i]）>0） {
			S[k].x = R[i].x;
			S[k].y = R[i].y;
			k++;
		}
	}

	return S;
}

int compare_by_x（const void* e1 const void* e2） {
	return （（POINT*）e1）->x - （（POINT*）e2）->x;
}

bool inTriangle（POINT* a POINT* b POINT* c POINT* k） {
	return line（a b k）*line（a b c） >= 0 && line（a c k）*line（a c

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

     文件      15289  2015-12-04 21:04  15S003062-杨煜-算法实验\实验1\fenzhisuanfa.cpp

     文件     290581  2015-11-16 16:43  15S003062-杨煜-算法实验\实验1.doc

     文件      14799  2015-12-01 23:01  15S003062-杨煜-算法实验\实验2\sousuosuanfa.cpp

     文件     245113  2015-11-20 21:00  15S003062-杨煜-算法实验\实验2.doc

     目录          0  2015-12-04 21:02  15S003062-杨煜-算法实验\实验1

     目录          0  2015-12-04 21:02  15S003062-杨煜-算法实验\实验2

     目录          0  2015-12-04 21:01  15S003062-杨煜-算法实验

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

               565782                    7