2 qq 22584569 qq_22584569 于 2016.04.21 19:17 提问

分治法解决因子分解及凸包问题 5C

![图片说明](https://img-ask.csdn.net/upload/201604/21/1461237380_398519.png)图片说明

题目2:在平面上有若干个点,编写程序求其凸包上的点以及由凸包所构成的多边形的面积。

输入要求:输入的第一行是一个整数n,表示点的个数。其后的n行,每行有两个整数,中间空格隔开,分别表示点的X,Y坐标。

输出要求:输出的第1行为一个整数m,表示凸包上点的个数,其后的m行每行有两个整数,分别表示凸包上点的坐标,最后一行为一个浮点数,精确到小数点后2位。

这是两道题目,都要求用分治法,第一题要求输出分解方法的个数及每种分解式。最好能给出流程图及时间复杂度,方便我这个小白理解

2个回答

devmiao
devmiao   Ds   Rxr 2016.04.21 22:44
qq_22584569
qq_22584569 这算法好像不对诶,C2373和C2065.
大约 2 年之前 回复
CSDNXIAON
CSDNXIAON   2016.04.21 19:22

凸包2:分治法解决凸包问题
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
分治法解决凸包问题
分治法就是吧一个大问题分成几个结构相同的子问题,再把子问题分解成更小的子问题.......      分治法解决凸包问题的大体思路就是,取横坐标最小的点p0和横坐标最大pn的点(这两个点一点在凸包上,这个仔细想想能想明白)然把这两个点连成一条直线,直线上面的半个凸包叫上凸包,直线下面的半个凸包叫下凸包,分别在上凸包和下凸包找出距离直线最大的点pmax,链接p1pmax和pnpmax如下图,又可以
利用分治法解决凸包问题
凸包的意思就是包含所有给定点的凸多边形。 ![这里写图片描述](http://img.blog.csdn.net/20170530091726010?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc2luYXRfMzYyNDYzNzE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gra
凸包2:分治法解决凸包问题
以下截图代码摘自《ACM程序设计培训教程 吴昊 中国铁道出版社》 : 上面代码中,resultList为全局变量,是最终凸包顶点集合,而leftList、rightList是局部变量。而且dealwith()函数中的insert(resultList,side,node)这个插入函数,是在边的起点和中点之间插入。例如上图15-9中,在边p1、pn之间插入pmax,下次在p1、pmax之间
分治法解决凸包问题(C语言实现)
先预排序,预排序后最左和最右的点肯定是凸包中的点。然后可以递归的从内向外扩展凸包,在当前直线的2侧寻找最高点,最高点肯定在凸包中,这里涉及到一些数学知识: a,首先定义射线p1到p2的左侧:若p1 p2 p构成的顺序是逆时针,称p在射线的左侧 b,三角形p1 p2 p3的面积等于下列行列式的一半: 仅当p3在射线p1p2左侧时这个值才为正。 由此我们很容易求p1,p2左侧的最高点(离直线最远的点,这个点即凸包向外扩展得到的新顶点),得到一个最高点后,就得到了2条新边,继续向外扩展
分治法求解凸包问题
利用分治法求解凸包问题!c语言 #include<stdio.h> #define PPmax 30 #define random(x) (rand()%x) typedef struct node{ float x,y; }Point; Point DingDian[PPmax];//用于存放凸边形的顶点 int DingDnum=0; typedef struct Pointss { Point p1,p2; }SDian;
分治法解决凸包问题(用C语言递归调用实现)
利用分治法解决凸包问题,递归调用,功能强悍,自己下载后在机器上跑一下
凸包问题之分治法
凸包:按横坐标排序,以最小点与最大点之间的连线为准,在直线一侧找使三角形面积最大的点,此点必在凸包内,以找到点与最大点或最小点继续递归以寻找最大三角形面积寻找凸包点,直至找不到符合条件的点。实现代码如下:#include&amp;lt;stdio.h&amp;gt; #include &amp;lt;stdlib.h&amp;gt; #include &amp;lt;windows.h&amp;gt; #define MAX_SIZE 100...
整数因子分解问题(分治法\C++实现)
Description 大于1的正整数 n 都可以分解为 n = x1 * x2 * ... * xm 例如:当n=12时,共有8种不同的分解式: 12 = 12 12 = 6*2 12 = 4*3 12 = 3*4 12 = 3*2*2 12 = 2*6 12 = 2*3*2 12 = 2*2*3 对于给定正整数n,计算n共有多少种不同的分解式。 Input 第一行一个正整数n (1<=n<=1000000) Output 不同的分解式数目 Sample Input 12 Sample Output 8 Hint 此题因子讲顺序的.第一个因子可能是2~n之间的数. 比如对12而言,第一个因子可能是2,3,4,6,12. 将第一个因子为2的分解个数,加上第一个因子为3的分解个数,...,直至加到第一个因子为12的分解个数. 而第一个因子为2的分解个数又是多少呢?是6(因为12/2=6)的分解个数,递归求解! 可用“递归”和“备忘录方法”两种方法分别求解,并测试一下效率。 递归实现整数因子分解的计数。 假设对正整数n的因子分解计数为solve(n)。 1)当n=1时,计数加1。 2)当n>1时,对每个因子i,计算solve(n/i)。
凸包问题的五种解法
前言:首先,什么是凸包? 假设平面上有p0~p12共13个点,过某些点作一个多边形,使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候,我们就叫它“凸包”。如下图: 然后,什么是凸包问题? 我们把这些点放在二维坐标系里面,那么每个点都能用 (x,y) 来表示。 现给出点的数目13,和各个点的坐标。求构成凸包的点? 解一:穷举法(蛮力法)时间复杂度:O(n³)。 思路:两点确
java另类分治法凸包问题
用的分治法的思想,凸包顶点正好可以构成循环,感觉比较新颖,就是不断顺时针旋转,按照书上那个公式不断找出左边的点和顶点,不断存入到数组中,最后的输出刚好是顺时针的输出,创建了好几个数组,其中还有一个三维数组,用法比较特殊,无意间想到的。。现在分享给大家,有兴趣的可以看看...By:imlyi