C++ 56ms Direct Solution: test if any of the inner angle is <= 180


  • 0
    S
    class Solution {
    public:
        #define PI  (3.1415926)
        // x2 y2 as base point and anti clock wise
        double getAngle(int x1, int y1, int x2, int y2) {
            if (x1 == x2) {
                return y2 > y1 ?270 :90;
            }
            if (y1 == y2) {
                return x2 > x1 ?180 :0;
            }
            int tmp = atan(abs(y1 - y2) / abs(x1 - x2)) * 180 / PI;
            if (x1 < x2 && y1 > y2) return 180 - tmp;
            if (x1 < x2 && y1 < y2) return 180 + tmp;
            if (x1 > x2 && y1 < y2) return 360 - tmp;
            return tmp;
        }
        
        //diff of clock wise from x1y1 to x3y3, with x2y2 as the base point
        double getDiff(int x1, int y1, int x2, int y2, int x3, int y3) {
            double angle1 = getAngle(x1, y1, x2, y2);
            double angle2 = getAngle(x3, y3, x2, y2);
            if (angle1 > angle2) return angle1 - angle2;
            if (angle1 < angle2)  return 360 - (angle2 -  angle1);
            return 0;
        }
        
        bool isConvex(vector<vector<int>>& points) {
            int n = points.size();
            if (n <= 3) return true;
            
            int less = 0, more = 0;
            for (int i = 0; i < n; i++) {
                int diff = getDiff(points[(i-1+n)%n][0], points[(i-1+n)%n][1], 
                                    points[i][0], points[i][1], 
                                    points[(i+1)%n][0], points[(i+1)%n][1]);
                
                if (diff < 180) less++;
                else if (diff > 180) more++;
                if (less && more) return false;
            }
            //cout << less <<" " << more << endl;
            return true;
        }
    };
    

  • 0

    @singku Good idea to calculate angles directly, but I think function call of atan is actually not really cheap and does floating point comparison of angles to 180.0 suffer numerical accuracy issues? Because even polygons with vertices of integers could have angles close to 180.0.


Log in to reply
 

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