240



步骤3:递归构造S11和S12的上包,然后简单地将它们连接起来,得到S1的上包。 同理,可以构造下包。
步骤4:在S2中要找的点是使得式(8-15)的值达到最小的那个点Pmin;
步骤5:连接0min,minn 1,找出S2中位于直线0min右边的点,这些点构成集合S21;找出S2中位于直线PminPn 1右边的点,这些点构成集合S22;△P0PminPn-1内部的点不予考虑。
步骤6:递归构造S21和S22的下包,然后简单地将它们连接起来,得到S2的下包。

3.算法描述
POINT P[N];//存放点集的数组 //构造S1的上包
void DC1(POINT P[],int min, int max) {
double smax=0,s; int i,a=0; //找点Pmax
for(i=min+1;i<max;i++) {//计算行列式的值
s=P[min].x*P[max].y+P[i].x*P[min].y+P[max].x*P[i].y
-P[i].x*P[max].y-P[max].x*P[min].y-P[min].x*P[i].y; if(s>smax) {smax=s;a=i;} } if(a!=0) {
printf("(%d,%d)\n",P[a].x,P[a].y);
DC1(P,min,a);//递归S11 DC1(P,a,max);//递归S12 } }
//构造S2的下包
void DC2(POINT P[],int min, int max) {
double s,smin=0; int i,b=0; //找点Pmin
for(i=min+1;i<max;i++)
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。数论算法及计算几何算法,凸包问题及最接近点对问题的分治法第八章 数论算法及计算几何算法 教学目标 ? ...
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。第八章 数论算法及计算几何算法 教学目标 ? 理解求最大公约数的算法 ? 掌握欧几里德公式的推广 ? ...
第八章 数论算法及计算几何算法 8.5 凸包问题 1、问题提出 ? 给定一个点集S={P0,P1,…,Pn-1},它的凸包是一 个最小的凸多边形P,且满足S中的每个点...
数论和计算几何_数学_自然科学_专业资料。pascal数论和计算几何数论和计算几何 ... 第八章 数论算法及计算几... 28页 免费 数论计算 引言 57页 免费 计算与...
第八章 数论算法及计算几... 28页 免费 奥数几何,数论,行程专题 8页 7...快速幂是用来快速计算a^n mod p的一种方 法。 如果n是偶数则a^n=a^(n/...
离散数学--11.1-2初等数论 24页 免费 数论-第八章 14页 1财富值 108第八章数论及其猜想的意... 41页 1财富值 第八章 数论算法及计算几何... 暂无...
第八章 数论算法及计算几何... 第九章 NP完全理论1/2 相关文档推荐 第2章 贪心法 56页 5财富值 第2章 贪心法 暂无评价 42页 1财富值 第2章 贪心法 ...
[编辑本段] 算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论 的算法、动态规划以及数值分析、加密算法、排序算法、检索...
三角形几何运算 7页 免费 第8章 数论算法及计算几何... 暂无评价 32页 免费 CAGD第八章曲线的几何处理... 5页 5财富值 计算几何 67页 免费喜欢此文档的...
224 第八章 数论算法及计算几何算法 ... 226 8.1 最大公约数......
热门文档