多角形の凸性判定

C++

こんにちは。

今回は多角形の凸性判定を投稿したいと思います。

是非最後までよろしくお願いします。

ソースコード

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

struct Point {
  double x;
  double y;
};

double dot(Point p0, Point p1, Point p2) {
  return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y);
}


double cross(Point p0, Point p1, Point p2) {
  return ( p1.x - p0.x ) * ( p2.y - p0.y ) - ( p2.x - p0.x) * (p1.y - p0.y);
}

bool isConvex(vector<Point> p) {
  int n = p.size();
  for(int i = 0; i < n; i++) {
    if( cross(p[(i + 1) % n], p[i % n], p[ (i + 2) % n]) > 0) {
      return false;
    }
  }
  return true;
}


int main(void) {
  int q;
  cin >> q;
  vector<Point> p;

  for(int i = 0; i < q; i++) {
    Point pi;
    cin >> pi.x >> pi.y;
    p.push_back(pi);
  }

  if(isConvex(p))
    cout << "1" << endl; //凸多角形の場合1を表示
  else
    cout << "0" << endl; //凸多角形でない場合0を表示

}

解説

bool isConvex(vector<Point> p) { //凸性を判定する関数
  int n = p.size();
  for(int i = 0; i < n; i++) {
    if( cross(p[(i + 1) % n], p[i % n], p[ (i + 2) % n]) > 0) {
      return false;
    }
  }
  return true;
}

breakは入りませんでしたね笑

頂点を反時計回りに巡回していき、時計回りか反時計回りを判定していきます。

自分のアルゴリズムでは反時計回りになっていったらそこで処理を終了して0を表示します。

コメント

タイトルとURLをコピーしました