建设网站需申请什么资料,wordpress调用用户昵称,哪里有做设备的,网站备案系统首先#xff0c;什么是凸包#xff1f; 假设平面上有p0~p12共13个点#xff0c;过某些点作一个多边形#xff0c;使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候#xff0c;我们就叫它“凸包”。 处理何种问题#xff1a;凸包可以看成在木板上钉许多…首先什么是凸包 假设平面上有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)。 思路应用分治法思想把一个大问题分成几个结构相同的子问题把子问题再分成几个更小的子问题……。然后我们就能用递归的方法分别求这些子问题的解。最后把每个子问题的解“组装”成原来大问题的解。 步骤
1.把所有的点都放在二维坐标系里面。那么横坐标最小和最大的两个点 P1 和 Pn 一定是凸包上的点为什么呢用反证法很容易证明这里不详讲。直线 P1Pn 把点集分成了两部分即 X 轴上面和下面两部分分别叫做上包和下包。 2.对上包求距离直线 P1Pn 最远的点即下图中的点 Pmax 。 3.作直线 P1Pmax 、PnPmax把直线 P1Pmax 左侧的点当成是上包把直线 PnPmax 右侧的点也当成是上包。 4.重复步骤 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。 最后栈中的元素就是凸包上的点了。
解五Melkman算法 说真的这个算法我也还没有看清。网上的资料也少的可怜我暂且把网上的解释截个图在这里往后搞懂以后再回来补上。 性能由一个快排Onlogn和一个遍历找点On总体时间复杂度为Onlogn。
原理
点Ax1y1Bx2y2
向量ABx2-x1y2-y1xy
向量的叉积a X b
通过结果的正负判断两矢量之间的顺逆时针关系
l 若a X b 0表示a在b的顺时针方向上
l 若a X b 0表示a在b的逆时针方向上
l 若a X b 0表示a与b共线但不确定方向是否相同
例如 A00
B22
C31
D2-1
AB22AC31AD2-1
AC X AB 32-12 40
AC在AB的顺时针方向上即点C在向量AB的下面。
实现步骤
排序按照x由小到大排序如果x相同按照y由小到大排序。 排序之后第一个点必为凸包上的点证明自己意淫一下有x最大、x最小、y最小、y最大的点都必在凸包上。 选最近两个刚入凸包的点再在排序中依次选点根据上面所提及到的原理判断该点在凸包那两点的顺时针还是逆时针方向。 如果在逆时针方向将该点加入凸包否则判定出之前进入凸包的点不合格删除该凸包点重复第三步直到该点加入凸包也就是说每个点都曾进过凸包只是后来有些被删了。 以上就是下凸包的构成步骤上凸包参考下凸包基本没有什么差别因为在判断时是判断是否为逆时针别误以为是在判段该点在向量的下方上凸包就不可用了对于逆时针而言都是一样的。 这种方法求出来的点是凸包沿着逆时针方向找出来的首位相接且第一个点重复两次所以除了点只有一个的情况下记得点的个数减一。
备注对于题目要求求凸包构成的面积时可以参考以下图示求法 输入样例解释
11—散点样例个数
5 8 —散点坐标
12 56
5 2
125 1
15 66
45 77
55 6
45 2
232 5
45 12
54 66
输出样例解释
tot7 —构成凸包点的个数
1: 5.00 , 2.00 —沿着凸包逆时针方向且保留两位小数
2: 125.00 , 1.00
3: 232.00 , 5.00
4: 45.00 , 77.00
5: 15.00 , 66.00
6: 12.00 , 56.00
7: 5.00 , 8.00
//求凸包时间复杂度nlogn
#includeiostream
#includecstdio
#includealgorithm
#includecmath
#includecstring
using namespace std;const int MaxN10010;int n,tot;//n为点的个数tot为凸点的个数
struct point
{double x,y;
};
point p[MaxN],CHP[MaxN];//CHP为凸包最后所构成的点bool cmp(point a,point b)//水平排序按x从大到小排如果x相同按y从大到小排序
{return (a.xb.x||(a.xb.xa.yb.y));
}double xmul(point a,point b,point c)//叉积
{return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}void Andrew()
{sort(p,pn,cmp);tot0;for(int i0; in; i) //计算下半个凸包{while(tot1xmul(CHP[tot-2],CHP[tot-1],p[i])0)--tot;CHP[tot]p[i];}int ktot;for(int in-2; i0; --i) //计算上半个凸包{while(totkxmul(CHP[tot-2],CHP[tot-1],p[i])0)--tot;CHP[tot]p[i];}if(n1)//对于只有一个点的包再单独判断--tot;
}int main()
{scanf(%d,n);for(int i0; in; i){scanf(%lf%lf,p[i].x,p[i].y);}Andrew();printf(tot%d\n,tot);for(int i0; itot; i){printf(%d: %.2lf , %.2lf\n,i1,CHP[i].x,CHP[i].y);}return 0;
}
一些预备知识点
首先在二维坐标下介绍一些定义 点Ax1y1Bx2y2
向量向量AB x2 - x1 , y2 - y1 ( x , y );
向量的模 |AB| sqrt ( xxyy );
向量的点积 结果为 x1x2 y1y2。
点积的结果是一个数值。
点积的集合意义我们以向量 a 向向量 b 做垂线则 | a | * cosa,b为 a 在向量 b 上的投影即点积是一个向量在另一个向量上的投影乘以另一个向量。且满足交换律
应用可以根据集合意义求两向量的夹角 cosa,b 向量a * 向量b / | a | * | b | x1x2 y1y2 / | a | * | b |
向量的叉积 结果为 x1y2-x2y1
叉积的结果也是一个向量是垂直于向量ab所形成的平面如果看成三维坐标的话是在 z 轴上上面结果是它的模。
方向判定右手定则右手半握大拇指垂直向上四指右向量a握向b大拇指的方向就是叉积的方向
叉积的集合意义1其结果是a和b为相邻边形成平行四边形的面积。
2结果有正有负有sinab可知和其夹角有关夹角大于180°为负值。
3叉积不满足交换律
应用
1通过结果的正负判断两矢量之间的顺逆时针关系
若 a x b 0表示a在b的顺时针方向上
若 a x b 0表示a在b的逆时针方向上
若 a x b 0表示a在b共线但不确定方向是否相同
