C++ easy to understand solution using triangles


  • 0
    C

    All triangles of a convex polygon should be walked in the same direction - either all clockwise, or all counterclockwise. And you need to skip midpoints on the same line. Performance is decent, it can be improved but I don't want to spend more time on it.

    class Solution {
        int countSum(vector<pair<int,int>>& points)
        {
            int sum = 0;
            for(int i = 0; i < points.size(); i++)
            {
                int x1 = points[i].first;
                int x2 = points[(i+1)%points.size()].first;
                int y1 = points[i].second;
                int y2 = points[(i+1)%points.size()].second;
                sum += (x2 - x1)*(y2 + y1);
            }
            return sum;
        }
        
    public:
        bool isConvex(vector<vector<int>>& points) {
            if(points.size() <= 3)
                return true;
            
            bool use_negative(false);
            int inc(1);
            int k1(1), k2(2);
            
            for(int k = 0; k < points.size(); )
            {
                vector<pair<int,int>> triangle { 
                        {points[k][0], points[k][1]},
                        {points[k1][0], points[k1][1]},
                        {points[k2][0], points[k2][1]},
                };
    
                int sum = countSum(triangle);
                    
                if(sum == 0)
                {
                    // skip adjacent points on the same line
                    k1 = (k1+1)%points.size();
                    k2 = (k2+1)%points.size();
                    inc++;
                }
                else
                {
                    if(k == 0 and sum < 0)
                        use_negative = true;
                    if(k > 0)
                    {
                        if(use_negative and sum > 0 or not use_negative and sum < 0)
                            return false;
                    }
                    k += inc;
                    inc = 1;
                    k1 = (k+1)%points.size();
                    k2 = (k+2)%points.size();
                }
            }
            return true;
        }
    };
    

Log in to reply
 

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