var monotone = {
    // 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
    // Returns a positive value, if OAB makes a counter-clockwise turn,
    // negative for clockwise turn, and zero if the points are collinea
    cross: function(o, a, b) {
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
    },

    convex_hull: function(points) {
        // Boring case: no points or a single point, possibly repeated multiple times.
        if (points.length <= 3)
            return false;

        // Build lower hull
        var lower = [], p;
        for (p in points) {
            while (lower.length >= 2 && this.cross(lower[lower.length - 2], lower[lower.length - 1], points[p]) <= 0)
                lower.pop();
            lower.push(points[p]);
        }

        // Build upper hull
        var upper = [];
        for (p in points.reverse()) {
            while (upper.length >= 2 && this.cross(upper[upper.length - 2], upper[upper.length - 1], points[p]) <= 0)
                upper.pop();
            upper.push(points[p]);
        }

        // Concatenation of the lower and upper hulls gives the convex hull.
        // Last point of each list is omitted because it is repeated at the beginning of the other list.
        upper.pop();
        lower.pop();
        var ret = [];
        for (p in lower)
            ret.push(lower[p]);
        for (p in upper)
            ret.push(upper[p]);

        return ret;
    }
};