LeetCode 469. 凸多边形(矢量交叉积)
最编程
2024-04-29 21:10:02
...
文章目录
- 1. 题目
- 2. 解题
1. 题目
给定一个按顺序连接的多边形的顶点,判断该多边形是否为凸多边形。
注:
顶点个数至少为 3 个且不超过 10,000。
坐标范围为 -10,000 到 10,000。
你可以假定给定的点形成的多边形均为简单多边形。
换句话说,保证每个顶点处恰好是两条边的汇合点,并且这些边 互不相交 。
示例 1:
[[0,0],[0,1],[1,1],[1,0]]
输出: True
解释:
示例 2:
[[0,0],[0,10],[10,10],[10,0],[5,5]]
输出: False
解释:
2. 解题
平面向量 向量积 定义 【平面向量】向量的叉积与三角形的面积
- 注意叉乘为0表示两个向量共线
[[0,0],[0,1],[1,1],[2,1],[2,2],[2,3],[3,3],[3,0]]
false
[[0,0],[1,0],[1,1],[-1,1],[-1,0]]
true
class Solution {
public:
bool isConvex(vector<vector<int>>& points) {
long long cur, prev = 0;
int i, n = points.size();
long long x1, y1, x2, y2;
for(i = 0; i < n; i++)
{
x1 = points[i][0]-points[(i+1)%n][0];
y1 = points[i][1]-points[(i+1)%n][1];
x2 = points[i][0]-points[(i+2)%n][0];
y2 = points[i][1]-points[(i+2)%n][1];
cur = x1*y2-x2*y1;
if(cur != 0)//两向量不共线
{
if(cur*prev < 0)//跟上次的方向不一样
return false;
prev = cur;
}
}
return true;
}
};
64 ms 15.5 MB
上一篇: 如何找到矢量产品 - 掘金