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

• 返回真

范例（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