> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/469-convex-polygon.md).

# 469 Convex Polygon

## 469. [Convex Polygon](https://leetcode.com/problems/convex-polygon/description/)

## 1. Question

Given a list of points that form a polygon when joined sequentially, find if this polygon is convex[(Convex polygon definition)](https://en.wikipedia.org/wiki/Convex_polygon).

**Note:**

1. There are at least 3 and at most 10,000 points.
2. Coordinates are in the range -10,000 to 10,000.
3. You may assume the polygon formed by given points is always a simple polygon [(Simple polygon definition)](https://en.wikipedia.org/wiki/Simple_polygon). In other words, we ensure that exactly two edges intersect at each vertex, and that edges otherwise **don't intersect each other**.

**Example 1:**

```
[[0,0],[0,1],[1,1],[1,0]]

Answer: True

Explanation:
```

![](https://2090187494-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LyrKyMPRGqB46Bg_cJ1%2F-LyrL-KnnBaE1T0K6SeT%2F-LyrLUCxzxZV2rLWjXsT%2Fconvexpolygon1.png?generation=1579329127026105\&alt=media)

**Example 2:**

```
[[0,0],[0,10],[10,10],[10,0],[5,5]]

Answer: False

Explanation:
```

![](https://2090187494-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LyrKyMPRGqB46Bg_cJ1%2F-LyrL-KnnBaE1T0K6SeT%2F-LyrLUCzcCUKTj2VNYz4%2Flc469covexpolygon2.png?generation=1579329126940044\&alt=media)

## 2. Implementation

**(1) Geometry**

思路: 凸多边形的定义是每个顶点的角度都小于180度, 判断一个多边形

要注意的地方有两点：(1)如果cross product是0，我们应该忽略，否则会影响之后的结果. (2)由于数字可能溢出，所以curCroosProduct和preCrossProduct要用long

```java
class Solution {
    public boolean isConvex(List<List<Integer>> points) {
        int n = points.size();
        long curCrossProduct = 0;
        long preCrossProduct = 0;

        for (int i = 0; i < n; i++) {
            List<Integer> pointA = points.get(i);
            List<Integer> pointB = points.get((i + 1) % n);
            List<Integer> pointC = points.get((i + 2) % n);

            curCrossProduct = getCrossProduct(pointA, pointB, pointC);

            if (curCrossProduct != 0) {
                if (curCrossProduct * preCrossProduct < 0) {
                    return false;
                }
                preCrossProduct = curCrossProduct;
            }
        }
        return true;
    }

    public int getCrossProduct(List<Integer> pointA, List<Integer> pointB, List<Integer> pointC) {
        int BAx = pointB.get(0) - pointA.get(0);
        int BAy = pointB.get(1) - pointA.get(1);
        int CAx = pointC.get(0) - pointA.get(0);
        int CAy = pointC.get(1) - pointA.get(1);

        return BAx * CAy - CAx * BAy;
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n), n是顶点的个数, 空间复杂度O(1)