C++ Polar Angle


  • 0

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

    0_1488681417939_Screenshot 2017-03-04 21.36.25.png

    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.

    0_1488681915804_Screenshot 2017-03-04 21.44.57.png

    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);
        }
    };
    

Log in to reply
 

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