graham扫描算法求凸包的c++源程序

Graham扫描算法 ： 大体思路是将不是凸包顶点的点从点集中去掉。 找出S中具有最小y坐标的点p（通过选取最左边的点打破平局） 根据点和p的连线 与 x轴正方向所成的角度，对S中的点进行排序（由小到大），并将p放在最前面。 从p点开始扫描排序后的S集合。如果这些点都在凸包上，则每三个相继的点p1,p2,p3满足以下性质：p3在向量<p1,p2>的左边.如果出现相继的三个点p1,p2,p3不满足上述性质，则p2点一定不是凸包的顶点，应立即去除。

/*	凸包问题：graham扫描算法实现
	程序未对重复点做特殊化处理。在GCC-4.4.5 （ubuntu 10.04）测试成功
	算法复杂度为O（n*log n） ，时间的主要部分是排序。
			lidachao 2011
*/
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAX 20         //给定的点的个数
//生成的点的在区域  [-RAND_max/2 RAND_max/2]X[-RAND_max/2 RAND_max/2] 内
#define RAND_max 20  
typedef struct point{
	float xy;
	float angle;
}point;
/******随机生成点，此处为简单起见用整型数作为测试数据*****/
void creatdata（ list * plist）{
	srand（time（0））;
	point p1;
	int i;
	for  （ i=0 ;i		int r1=random（）%RAND_max-RAND_max/2r2=random（）%RAND_max-RAND_max/2;
		p1.x=float（r1）;p1.y=float（r2）;
		plist->push_back（p1）;
	}
}
/*****计算向量（x1y1）和（x2y2）的夹角余弦值*******/
float vectors_cos（float x1float y1float x2float y2）{
	return