# 469. Convex Polygon

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: bool isConvex(vector>& points) { auto getCross = [](const vector& p, const vector& q, const vector& r) -> int { return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0]); }; const int n = points.size(); long sign = 0; for (int i = 0; i < points.size(); ++i) { const int cross = getCross(points[i], points[(i + 1) % n], points[(i + 2) % n]); if (cross == 0) // P, q, r are collinear continue; if (sign == 0) // Find first cross that's not 0 sign = cross; else if (cross * sign < 0) return false; } return true; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public boolean isConvex(List> points) { final int n = points.size(); long sign = 0; for (int i = 0; i < n; ++i) { final int cross = getCross(points.get(i), points.get((i + 1) % n), points.get((i + 2) % n)); if (cross == 0) // P, q, r are collinear continue; if (sign == 0) // Find first cross that's not 0 sign = cross; else if (cross * sign < 0) return false; } return true; } private int getCross(List p, List q, List r) { return (q.get(0) - p.get(0)) * (r.get(1) - p.get(1)) - (q.get(1) - p.get(1)) * (r.get(0) - p.get(0)); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def isConvex(self, points: List[List[int]]) -> bool: # Pq x qr def getCross(p: List[int], q: List[int], r: List[int]): return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0]) sign = 0 for i in range(len(points)): cross = getCross(points[i - 2], points[i - 1], points[i]) if cross == 0: # P, q, r are collinear continue if sign == 0: # Find first cross that's not 0 sign = cross elif cross * sign < 0: return False return True