徐州市鼓楼区建设局网站,中国电信黄页app,做 理财网站,wordpress更换主题显示不出来原文地址#xff1a;http://blog.csdn.net/suwei19870312/article/details/542281 基本问题#xff1a; 平面上有n个点p1,p2, ..., pn, 要求求出一个面积最小的凸多边形#xff0c;使得这个多边形包含所有平面上的点。 根据算法导论上提供的两个方法做一些介绍#xff1a; …原文地址http://blog.csdn.net/suwei19870312/article/details/542281 基本问题 平面上有n个点p1,p2, ..., pn, 要求求出一个面积最小的凸多边形使得这个多边形包含所有平面上的点。 根据算法导论上提供的两个方法做一些介绍 算法1 Graham扫描法 下面直接给出一段伪代码方便描述 GRAHAM-SCAN(Q)
{1. 取出所有点钟y坐标最小的点作为初始点p02. 之后对于所有其他点以p0为中心点集中的所有点按关于p0的极角逆时针排序,形成p1,p2,..pn-13. push(p0,S) 4. push(p1,S)5. push(P2.S)for(i: 3-m){ px nexttoTop(S)py Top(S) do while (如果(py-pi向量)相对于(px-py向量)是向右走的)pop(S)px nextotTop(S)py Top(S)push(pi, S);}return S;
}最后S栈中保存了所有凸多边形的顶点集合 下面用图示表示一下算法的过程 1.初始化所有的p0,p1,...pn-1 2. p0p1,p2入栈 3. 这时候栈顶元素是p2,次栈顶元素p1, 枚举p3, 那么可以看出 p2-p3的向量相对于p2-p1的向量是向右走的所以栈中弹出p2, 压入p3 4. P4入栈由于栈顶元素是p3次栈顶元素是p1, 那么p3-p4向量相对于p1-p3向量是向左走的所以压入p4 5.由于栈顶元素是p4次栈顶元素是p3, 那么p4-p5向量相对于p3-p4向量是向右走的所以弹出p4,压入p5 //xiaoxia版
#include stdio.h
#include math.h
#include stdlib.h
typedef struct
{double x;double y;
}POINT;
POINT result[102]; //保存凸包上的点相当于所说的栈S
POINT a[102];
int n,top;
double Distance(POINT p1,POINT p2) //两点间的距离
{return sqrt((p1.x-p2.x)*(p1.x-p2.x)(p1.y-p2.y)*(p1.y-p2.y));
}
double Multiply(POINT p1,POINT p2,POINT p3) //叉积
{ return ((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));
}
int Compare(const void *p1,const void *p2) //根据p0-p1的极值和p0-p2的极值进行比较如果极值相同则用距离长度比较
{POINT *p3,*p4;double m;p3(POINT *)p1; p4(POINT *)p2; mMultiply(a[0],*p3,*p4) ;if(m0) return 1;else if(m0(Distance(a[0],*p3)Distance(a[0],*p4)))return 1;else return -1;
}
//寻找凸包的过程p0,p1,p2..的寻找过程在下面main中进行了
void Tubao()
{int i;result[0].xa[0].x;result[0].ya[0].y;result[1].xa[1].x;result[1].ya[1].y;result[2].xa[2].x;result[2].ya[2].y;top2;for(i3;in;i){while(Multiply(result[top-1],result[top],a[i])0 top2)top--;result[top1].xa[i].x;result[top1].ya[i].y;top;}
}
int main()
{int i,p;double px,py,len,temp;while(scanf(%d,n)!EOF,n){for(i0;in;i)scanf(%lf%lf,a[i].x,a[i].y);if(n1){printf(0.00/n);continue;}else if(n2){printf(%.2lf/n,Distance(a[0],a[1]));continue;}//这里的目的好像是找出y坐标最小的点之后把他定义为P0 py-1;for(i0;in;i){if(py-1 || a[i].ypy){pxa[i].x;pya[i].y;pi;}else if(a[i].ypy a[i].xpx){pxa[i].x;pya[i].y;pi;}}//swap(a[0],a[p])tempa[0].x;a[0].xa[p].x;a[p].xtemp;tempa[0].y;a[0].ya[p].y;a[p].ytemp;//用叉乘来实现排序的比较 qsort(a[1],n-1,sizeof(double)*2,Compare);a[n].xa[0].x;a[n].ya[0].y;//调用tubao Tubao();len0.0;for(i0;itop;i)lenlenDistance(result[i],result[i1]);printf(%.2lf/n,len);}return 0;
}算法学习不断 转载于:https://www.cnblogs.com/Jason-Damon/archive/2011/10/14/2211058.html
