# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/google/469-convex-polygon.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.