凸性判定

説明

与えられた多角形 P が凸かどうかを判定する．一周回ってみて，右向きの辺がないことを確かめればよい．

計算量

O(n)．

ソースコード

#define curr(P, i) P[(i) % P.size()]
#define next(P, i) P[(i+1) % P.size()]
#define prev(P, i) P[(i+P.size()-1) % P.size()]
bool isconvex(const polygon &P) {
  for (int i = 0; i < P.size(); ++i)
    if (ccw(prev(P, i), curr(P, i), next(P, i)) > 0) return false;
  return true;
}

Verified

• UVA 10078 (The Art Gallery), 0.004 sec, 468 kb