数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中的凸多边形
假设我们有一系列点，这些点按顺序连接起来形成一个多边形，我们需要判断这个多边形是否是凸多边形（凸多边形的定义）。需要注意的是，点的数量至少为3，最多为10,000个。坐标范围在-10,000到10,000之间。
我们可以假设由给定点形成的多边形始终是一个简单多边形，换句话说，我们确保在每个顶点处恰好有两个边相交，并且边在其他地方不相交。因此，如果输入类似于：[[0,0],[0,1],[1,1],[1,0]]，则它是凸的，返回的值将为true。
为了解决这个问题，我们将遵循以下步骤：
定义一个方法calc()，它将接收ax, ay, bx, by, cx, cy作为参数，其工作原理如下：
BAx := ax – bx, BAy := ay – by, BCx := cx – bx, BCy := cy - by
在主方法中执行以下操作：
neg := false，pos := false，n := 点数组的大小
对于i从0到n – 1
a := i，b := (i + 1) mod n，c := (i + 2) mod n
cross_prod := calc(p[a, 0], p[a, 1], p[b, 0], p[b, 1], p[c, 0], p[c, 1])
如果cross_prod < 0，则neg := true，否则如果cross_prod > 0，则pos := true
如果neg和pos都为true，则返回false
返回true
示例 (C++)
让我们看下面的实现来更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isConvex(vector<vector<int>>& points) {
bool neg = false;
bool pos = false;
int n = points.size();
for(int i = 0; i < n; i++){
int a = i;
int b = (i + 1) % n;
int c = (i + 2) % n;
int crossProduct = calc(points[a][0], points[a][1], points[b][0], points[b][1], points[c][0], points[c][1]);
if(crossProduct < 0) neg = true;
else if(crossProduct > 0) pos = true;
if(neg && pos) return false;
}
return true;
}
int calc(int ax, int ay, int bx, int by, int cx, int cy){
int BAx = ax - bx;
int BAy = ay - by;
int BCx = cx - bx;
int BCy = cy - by;
return (BAx * BCy - BAy * BCx);
}
};
main(){
vector<vector<int>> v = {{0,0},{0,1},{1,1},{1,0}};
Solution ob;
cout << (ob.isConvex(v));
}输入
[[0,0],[0,1],[1,1],[1,0]]
输出
1
更新于：2020年4月29日
2K+ 次浏览
广告