建筑网片规格介绍,大庆网站建设优化,课程中心网站建设内容,做h的游戏视频网站转载自#xff1a;https://blog.csdn.net/bone_ace/article/details/46239187 凸包问题的五种解法 2015年05月29日 17:58:51 阅读数#xff1a;33660前言#xff1a; 首先#xff0c;什么是凸包#xff1f; 假设平面上有p0~p12共13个点#xff0c;过某些点作一个多边形https://blog.csdn.net/bone_ace/article/details/46239187 凸包问题的五种解法 2015年05月29日 17:58:51 阅读数33660 前言 首先什么是凸包 假设平面上有p0~p12共13个点过某些点作一个多边形使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候我们就叫它“凸包”。如下图 然后什么是凸包问题 我们把这些点放在二维坐标系里面那么每个点都能用 (x,y) 来表示。 现给出点的数目13和各个点的坐标。求构成凸包的点 解一穷举法蛮力法 时间复杂度O(n³。 思路两点确定一条直线如果剩余的其它点都在这条直线的同一侧则这两个点是凸包上的点否则就不是。 步骤 将点集里面的所有点两两配对组成 n(n-1)/2 条直线。对于每条直线再检查剩余的 (n-2) 个点是否在直线的同一侧。如何判断一个点 p3 是在直线 p1p2 的左边还是右边呢坐标p1(x1,y1)p2(x2,y2)p3(x3,y3) 当上式结果为正时p3在直线 p1p2 的左侧当结果为负时p3在直线 p1p2 的右边。 解二分治法 时间复杂度O(n㏒n)。 思路应用分治法思想把一个大问题分成几个结构相同的子问题把子问题再分成几个更小的子问题……。然后我们就能用递归的方法分别求这些子问题的解。最后把每个子问题的解“组装”成原来大问题的解。 步骤 把所有的点都放在二维坐标系里面。那么横坐标最小和最大的两个点 P1 和 Pn 一定是凸包上的点为什么呢用反证法很容易证明这里不详讲。直线 P1Pn 把点集分成了两部分即 X 轴上面和下面两部分分别叫做上包和下包。对上包求距离直线 P1Pn 最远的点即下图中的点 Pmax 。作直线 P1Pmax 、PnPmax把直线 P1Pmax 左侧的点当成是上包把直线 PnPmax 右侧的点也当成是上包。重复步骤 2、3。对下包也作类似操作。 然而怎么求距离某直线最远的点呢我们还是用到解一中的公式 设有一个点 P3 和直线 P1P2 。坐标p1(x1,y1)p2(x2,y2)p3(x3,y3) 对上式的结果取绝对值绝对值越大则距离直线越远。 注意在步骤一如果横坐标最小的点不止一个那么这几个点都是凸包上的点此时上包和下包的划分就有点不同了需要注意。 解三Jarvis步进法 时间复杂度O(nH)。其中 n 是点的总个数H 是凸包上的点的个数 思路 纵坐标最小的那个点一定是凸包上的点例如图上的 P0。从 P0 开始按逆时针的方向逐个找凸包上的点每前进一步找到一个点所以叫作步进法。怎么找下一个点呢利用夹角。假设现在已经找到 {P0P1P2} 了要找下一个点剩下的点分别和 P2 组成向量设这个向量与向量P1P2的夹角为 β 。当 β 最小时就是所要求的下一个点了此处为 P3 。 注意 找第二个点 P1 时因为已经找到的只有 P0 一个点所以向量只能和水平线作夹角 α当 α 最小时求得第二个点。共线情况如果直线 P2P3 上还有一个点 P4即三个点共线此时由向量P2P3 和向量P2P4 产生的两个 β 是相同的。我们应该把 P3、P4 都当做凸包上的点并且把距离 P2 最远的那个点即图中的P4作为最后搜索到的点继续找它的下一个连接点。 解四Graham扫描法 时间复杂度O(n㏒n) 思路Graham扫描的思想和Jarris步进法类似也是先找到凸包上的一个点然后从那个点开始按逆时针方向逐个找凸包上的点但它不是利用夹角。 步骤 把所有点放在二维坐标系中则纵坐标最小的点一定是凸包上的点如图中的P0。把所有点的坐标平移一下使 P0 作为原点如上图。计算各个点相对于 P0 的幅角 α 按从小到大的顺序对各个点排序。当 α 相同时距离 P0 比较近的排在前面。例如上图得到的结果为 P1P2P3P4P5P6P7P8。我们由几何知识可以知道结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。 以上是准备步骤以下开始求凸包 以上我们已经知道了凸包上的第一个点 P0 和第二个点 P1我们把它们放在栈里面。现在从步骤3求得的那个结果里把 P1 后面的那个点拿出来做当前点即 P2 。接下来开始找第三个点连接P0和栈顶的那个点得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5如果在直线上或者在直线的左边就执行步骤6。如果在右边则栈顶的那个元素不是凸包上的点把栈顶元素出栈。执行步骤4。当前点是凸包上的点把它压入栈执行步骤7。检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点返回步骤4。最后栈中的元素就是凸包上的点了。 以下为用Graham扫描法动态求解的过程 代码poj1873 #includecstdio
#includealgorithm
#includecmath
#includecstring
#includevector
#define zero(a) (fabs((double)(a))(1e-8))
using namespace std;
const int eps1e-8;
struct tr{int x,y,v,l;
}s1[20],s[20];
int st[20];
int mul(tr p,tr u,tr v){//求叉积 return (p.x-u.x)*(v.y-u.y)-(v.x-u.x)*(p.y-u.y);
}
double dis(tr a,tr b){//求长度 return sqrt((double)(a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y));
}
bool cmp(tr a,tr b){//极角排序 if(mul(a,s[0],b)0)//以最小点s[0]为基准排序 return true;else if(zero(mul(a,s[0],b))dis(s[0],a)dis(s[0],b))return true;return false;
}
int mv,ct,nt;
double l2;
int do1(int n,int l1,int mv1,int c){int i,j;int x,y;double l;//要用的木材长度 if(n1){l0;}/*else if(n2){ldis(s[0],s[1])*2;}*/ else{ l0;for(i1;in;i){if(s[0].ys[i].y||(s[0].ys[i].ys[0].xs[i].x)){//将s[0]化为最小点以便极角排序 swap(s[0],s[i]);}}sort(s1,sn,cmp);//排序 int top,cnt;st[0]0;st[1]1;tr a,b;top2;cnt2;while(cntn-1){//当 st[top]cnt;//先放入当前点 top;cnt;as[st[top-1]];bs[st[top-2]];while(mul(s[cnt],a,b)eps){//以当前点的下一个点为标杆点来除去不合凸包条件的点Graham扫描法如果标杆点在当前栈顶的两个点组成的直线的右边则说明栈顶的点不是凸包上的点 top--;//去掉不合条件的点 ab;//重新判断当前栈顶的点 bs[st[top-2]];}}st[top]n-1;//压入最后一次的标杆点它一定是凸包上的点因为它在最左边 for( i0;itop-1;i){ldis(s[st[i]],s[st[i1]]);}ldis(s[0],s[n-1]);//把这句代码写成了ldis(s[st[0]],s[st[n-1]]),卡了三个小时QAQ引以为戒啊 }//printf(%d %d\n,l1,l);if((l1-l)0){// 砍掉的树可以把剩下的树围起来 if(mv1mv){//剩下树的价值要最大 l2l1-l;ntn;mvmv1;ctc;}else if(mv1mvntn){//价值相同时砍掉的树要最少 l2l1-l;ntn;mvmv1;ctc;}}return 0;
}
int main(){int n,i,j,k0;int a,b,cnt,c;int mv1;while(scanf(%d,n)!EOFn){k;nt0;for(i0;in;i){scanf(%d%d%d%d,s1[i].x,s1[i].y,s1[i].v,s1[i].l);}mv0;ct0;for(j1;j(1n)-1;j){//二进制枚举 //printf(%d\n,j);aj,b0;cnt0;mv10;int l10;for(i0;in;i){if(((1i)j)){//按位与 s[cnt]s1[i];//放入不砍的树 mv1s1[i].v;//剩余的价值 }else{l1s1[i].l;//可以做篱笆的长度 }}if(mvmv1)//剩下的价值小于最优的价值 continue;do1(cnt,l1,mv1,j);}printf(Forest %d\n,k);printf(Cut these trees:);for(i0;in;i)if(!((1i)ct)) printf( %d,i1);printf(\n);printf(Extra wood: %.2f\n\n,l2);}return 0;
}解五Melkman算法 说真的这个算法我也还没有看清。网上的资料也少的可怜我暂且把网上的解释截个图在这里往后搞懂以后再回来补上。 或者有人看懂了的希望不吝指教不甚感激 扩展 以上讨论的只是二维的凸包如果延生为三维、多维的凸包问题呢如何求解 不过首先二维凸包可以用来解决围栏问题、城市规划问题、聚类分析等等。但是三维、多维的凸包可能的使用范畴有哪些 转载于:https://www.cnblogs.com/cglongge/p/9408417.html
