ei1333's page

凸多角形判定

説明

与えられた多角形が凸多角形かどうか判定する。点を順番に見ていき隣接 $3$ 点について点の進行方向が逆向きのものがないか確かめれば良い。

計算量

$O(N)$

実装例

bool IsConvex(const Polygon& p){
  int n = p.size();
  for(int i = 0; i < n; i++){
    if(ccw(p[(i + n - 1) % n], p[i], p[(i + 1) % n]) == -1) return false;
  }
  return true;
}