本文共 1517 字，大约阅读时间需要 5 分钟。
//Memory Time// 1347K 0MS// by : Snarl_jsb#include #include #include #include #include #include #include #include #include #include #include #include #define MAX 1100#define N 1000#define INF 1000000#define LL long longusing namespace std;struct point{ int x,y; //横纵坐标 : x,y double len,theta; //与参考点的距离 len 与参考点构成的向量与 (1,0)向量构成的夹角的余弦值 theta}g[N]; //定义了一个全局变量，记录凸包中的点/*--------按余弦值，从大到小快速排序--------*/void qsort(int st,int en){ int i=st,j=en; g[0]=g[i]; while(i =g[j].theta) j--; if(i g[k].len) k=p+1; p++; } map[++tot]=g[k]; p++; } /*第四步，对map中的元素扫描一遍，确定凸包的元素，放在数组g中*/ *n=tot; tot=3; //先做了一个小小的处理，使得自己更好理解 memset(g,0,sizeof(g)); g[1]=map[1]; g[2]=map[2]; g[3]=map[3]; //先将前三个点入栈 g for(int i=4;i<=*n;i++) //依次用map中的每个点对g中的点进行一次判断，看是否是属于凸包 { double chaji=(g[tot].x-g[tot-1].x)*(map[i].y-g[tot].y)-(map[i].x-g[tot].x)*(g[tot].y-g[tot-1].y); for(;chaji<=0 && tot>=1;) //如果旋转的方向不同，g[tot]这个点就不是，删除,并继续判断 g 中下一个点是不是 { tot--; chaji=(g[tot].x-g[tot-1].x)*(map[i].y-g[tot].y)-(map[i].x-g[tot].x)*(g[tot].y-g[tot-1].y); } g[++tot]=map[i]; //将map[i]这个点入栈，至于是否是属于凸包中的点，等待以后的点来判断 } *n=tot;//凸包处理完，总共有tot个凸包上的点}int main(){ //freopen("C:/Users/chengfeng/Desktop/in.txt","r",stdin); int n; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d%d",&g[i].x,&g[i].y); graham(&n); for(int i=1;i<=n;i++) printf("(%d,%2d)\n",g[i].x,g[i].y); } return 0;}
转载于:https://www.cnblogs.com/crazyacking/p/3915511.html