C++ Polar Angle

• Given `N` points, and hence `N` vectors, the polar angles of the vectors must be sorted (possibly rotated).

In this example, although the polar angles are not sorted, but its rotation `[0, 0, pi/2, 3pi/4, 5pi/4, 3pi/2]` is sorted. So this is a convex polygon.

``````class Solution {
public:
bool isConvex(vector<vector<int>>& A) {
int N = A.size(); // N = number of points / number of vectors
constexpr double PI = atan(1.0) * 4.0; // constant PI

vector<double> polars; // polar angle

// Calculate the polar angle of all N vectors
for (int i = 0; i < A.size(); i++) {
int dx = A[(i+1)%N][0] - A[i][0];
int dy = A[(i+1)%N][1] - A[i][1];
// An angle in range [0, 2*PI) is obtained by adding 2*PI if it is negative.
double temp = atan2(dy, dx);
polars.push_back(temp >= 0 ? temp : temp + 2*PI);
}

// The polar angles must be nondecreasing or nonincreasing (possibly rotated)
// E.g. polar = [0.4, 0.5, 0.1, 0.2, 0.3] is OK
int up = 0;
int down = 0;
for (int i = 0; i < polars.size(); i++) {
if (polars[(i+1)%N] > polars[i]) up++;
if (polars[(i+1)%N] < polars[i]) down++;
}
return (up <= 1 || down <= 1);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.