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）modn和c：=（i+2）modn
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
返回真
范例（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