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 :=점 배열의 크기
0 ~ n – 1 범위의 i에 대해
- 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]]

C++의 볼록 다각형

예시(C++)

입력

출력