#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