Codility lessons solutions

PolygonConcavityIndex.cpp

#include <algorithm>

static int sign(int64_t v) { return (0 < v) - (v < 0); };

static int rotDir (const Point2D& a, const Point2D& b, const Point2D& c) {
    return sign(int64_t(b.x - a.x)*int64_t(c.y - a.y) - int64_t(b.y - a.y)*int64_t(c.x - a.x));
} 

int solution(vector<Point2D> &A) {
    if (A.size() < 3) return -1;
    
    auto getNext = [&A](const vector<Point2D>::iterator& c) { 
        return (next(c) == A.end()) ? A.begin() : next(c);
    };
    auto getPrev = [&A](const vector<Point2D>::iterator& c) { 
        return (c == A.begin()) ? prev(A.end()) : prev(c);
    };

    
    //find extreme(bottom) point which lies on the convex hull for sure
    auto startIt = min_element(begin(A), end(A), [](const Point2D& a, const Point2D b) {
        return a.y < b.y;
    });
    
    auto prevIt = getPrev(startIt);
    auto currIt = startIt;
    auto nextIt = getNext(startIt);
    int dir;
    //find first point which do not lies on a line
    while ( (dir = rotDir( *prevIt, *currIt, *nextIt )) == 0 ) {
        prevIt = currIt;
        currIt = nextIt;
        nextIt = getNext(nextIt);
        if (nextIt != startIt) return -1; //All points lie on a common line 
    }
    
    do {
        prevIt = currIt;
        currIt = nextIt;
        nextIt = getNext(nextIt);
        if ( (dir + rotDir(*prevIt, *currIt, *nextIt )) == 0 ) //We've found a contrary rotation
            return distance(begin(A), currIt);
    } while (currIt != startIt);
    
    return -1;//All rotations were in the same direction
}