补充知识:向量叉积,向量P = (x1, y1); Q = (x2, y2); P×Q = (x1*y2 - x2*y1);
叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:
若 P × Q > 0 , 则P在Q的顺时针方向。
若 P × Q < 0 , 则P在Q的逆时针方向。
若 P × Q = 0 , 则P与Q共线,但可能同向也可能反向。
叉积的方向与进行叉积的两个向量都垂直,所以叉积向量即为这两个向量构成平面的法向量。
我们来考虑题目,假设凸多边形各个定点坐标按照逆时针方向存储于一个数组中,那么可以通过计算0-i与0-P两个向量之间的左右关系确定点P于某两个相邻的顶点构成的向量之间,如O-x与o-(x-1),然后看是否(x-1)-p向量位于(x-1)-x向量的逆时针方向,如果是顺时针方向则不在凸多边形内。
double multiply(Point& p1, Point& p2, Point& p0) { return (p1.x - p0.x) * (p2.y - p0.y)*1.0 - (p1.y - p0.y) * (p2.x - p0.x)*1.0; } bool inConvexPolygon(vector<Point> Polygon, Point target) { int len = Polygon.size(); if (multiply(target, Polygon[1], Polygon[0]) > 0 && multiply(target, Polygon[len - 1], Polygon[0]) < 0) { return false; } int s = 1, e = len -1; int line = -1; while (s <= e) { int m = s + ((e-s) >> 1); if (multiply(target, Polygon[m], Polygon[0]) > 0) { // target在m顺时针方向 line = m; // line保存的是m逆时针方向后的第一个点 e = m -1; } else { // target在m逆时针方向 s = m + 1; } } return multiply(Polygon[line], target, Polygon[line -1]) > 0; }
相关推荐
时间复杂度为O(logN)的常用算法,算法数据结构 五大常用算法
撸一个std::lower_bound,不断优化,直到最坏复杂度也为O(logN) 什么是LRU缓存,怎么实现 实现二叉树的层序遍历再按层输出 实现 怎么实现线程池 实现一个二叉树的持久化方案,可以伪代码,必须用指针 编程实现单例...
时间复杂度为O(logN)的排序算法。。俗称重口味排序
快速幂 基于java实现的快速幂、快速乘算法,利用二进制位运算将O(n)的算法复杂度降到O(logn)
| _O(n)_ ~ _O(n^2)_ | _O(n)_ | Medium || Bit Manipulation, Counting Sort, Pruning| 342 | [Power of Four](https://leetcode.com/problems/power-of-four/) | [C++](./C++/power-of-four.cpp) [Python](./...
1-4在任何情况下,时间复杂度为O(n2) 的算法比时间复杂度为O(n*logn)的算法所花费的时间都长。F 1-5对n个整数排序,在最坏的情况下,不能保证以少于O(n)的时间完成。T 1-6用渐进表示法分析算法复杂度的增长...
| 判断点 Q 是否在多边形内 35 | 计算多边形的面积 35 | 解二次方程 AX^2+BX+C=0 36 | 计算直线的一般式 AX+BY+C=0 36 | 点到直线距离 36 | 直线与圆的交点,已知直线与圆相交 36 | 点是否在射线的正向 36 | ...
2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作; 3.递归地...
已知(k1, k2, …, kp)是堆,则可以写一个时间复杂度为O(logn)的算法,将(k1, k2, …, kp, kp+1)调整为堆。试编写“从p=1起,逐个插入建堆”的算法,并讨论由此方法建堆的时间复杂度。
用于快速判断一个32位无符号整数在哪一个区间,实现了恒常时间复杂度O(1)的求解算法:每次判断只需要恒定的四步就立即给出结果。区间数目越大,相比于二分折半O(logN)的优势也越大,数据量小可能不明显。本实现适合...
优先队列使用 O(LogN) 复杂度为测试类实现 PriorityQueue。
由于一棵有n个结点的红黑树的高度为O(logn),因此RB-NSERT的第1~16行要花费O(logn)时间。在 RB-INSERT-FIXUP中,仅当情况1发生,然后指 针z沿着树上升2层,whle循环才会重复执行。所以whe循环可能被执行的总次数为O(logn...
排序算法 多种排序算法O(n * logn)
logn.jsp
具有有效O(1)附加和O(logN)证明的哈希链。 作为python client.py kafka_host:kafka_port ,例如 python client.py 192.168.1.110:9092 或者 python client.py kafka.network.hostname:9092
O(logn) O(logn) - O(logn) O(n) 无序集 O(1)Average O(n)Worst O(1)Average O(n)Worst - O(1)Average O(n)Worst O(n) 地图 O(logn) O(logn) - O(logn) O(n) 无序映射 O(1)Average O(n)Worst O(1)Average O(n)Worst ...
而插入操作,只要判断应该插入那棵树,也将是O(1),然而之后需要调整,此时的时间复杂度在O(logN) 内。 删除操作,也是将数组中的第一个数删除。O(1),删除之后,调整堆时,时间复杂度也在O(logN)内。
leetcode走楼梯 Practice Data Structures and Algorithms Table of content tags LC Question and Solution List ...O(?...O(?...O(logn) O(1) binary search standard Easy Binary Search 814 O(n) O(n
深入浅出,描述java算法,从0到1。 1.大O表示法:粗略的量度方法即算法的速度是如何与数据项的个数相关的 算法 大O表示法表示的运行时间 ...O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到)
以 N 为底的对数 LogN(X) = Log(X) / Log(N) 7.正则表达式相关: 操作符: \ 转义符 (), (?:), (?=), [] 圆括号和方括号 *, +, ?, {n}, {n,}, {n,m} 限定符 ^, $, \anymetacharacter 位置和顺序 | “或...