public class ConvexHull {
    public static double orientation(Point p1, Point p2, Point p3) {
        double val;
        //p1=p l p2=q l p3 = r
        //val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
        //val = -p2.x*p1.y + p3.x*p1.y + p1.x*p2.y - p3.x*p2.y - p1.x*p3.y + p2.x*p3.y;
        val = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
        return val;

        /*
        // orientation is to the left-hand side
        if (val > 0)
            return -1;

        // orientation is to the right-hand side
        if (val < 0)
            return 1;

        // orientation is neutral
        return 0;*/
    }

    public static Point[] giftWrap(Point[] pointSet) {
        if (pointSet.length < 3){
            return pointSet;
        }

        // Find the leftmost point
        int l = 0;
        for (int i = 1; i < pointSet.length; i++) {
            if (pointSet[i].x < pointSet[l].x){
                l = i;
            }
        }
        Point pointOnHull = pointSet[l];

        Point[] hull = new Point[pointSet.length];
        Point endPoint;
        int len = 0;
        do {
            hull[len] = pointOnHull;
            endPoint = pointSet[0];
            for (int i = 1; i < pointSet.length; i++){
                if ((endPoint == pointOnHull) || (orientation(pointOnHull, endPoint, pointSet[i]) > 0)){
                    endPoint = pointSet[i];
                }
            }
            len++;
            pointOnHull = endPoint;
        } while (endPoint != hull[0]);

        Point[] result = new Point[len];
        for(int i = 0; i < len; i++){
            result[i] = hull[i];
        }
        return result;
    }