public class GrahamScan
{
    private Point[] p;
    private int n;
    private int h;

    public int computeHull(Point[] p)
    {
        this.p=p;
        n=p.length;
        if (n<3) return n;
        h=0;
        grahamScan();
        return h;
    }

    private void grahamScan()
    {
        exchange(0, indexOfLowestPoint());
        Point pl=new Point(p[0]);
        makeRelTo(pl);
        sort();
        makeRelTo(pl.reversed());
        int i=3, k=3;
        while (k<n)
        {
            exchange(i, k);
            while (!isConvex(i-1))
                exchange(i-1, i--);
            k++;
            i++;
        }
        h=i;
    }

    private void exchange(int i, int j)
    {
        Point t=p[i];
        p[i]=p[j];
        p[j]=t;
    }

    private void makeRelTo(Point p0)
    {
        int i;
        Point p1=new Point(p0); // notwendig, weil p0 in p[] sein kann
        for (i=0; i<n; i++)
            p[i].makeRelTo(p1);
    }

    private int indexOfLowestPoint()
    {
        int i, min=0;
        for (i=1; i<n; i++)
            if (p[i].y<p[min].y || p[i].y==p[min].y && p[i].x<p[min].x)
                min=i;
        return min;
    }

    private boolean isConvex(int i)
    {
        return p[i].isConvex(p[i-1], p[i+1]);
    }

    private void sort()
    {
        quicksort(1, n-1); // ohne Punkt 0
    }

    private void quicksort(int lo, int hi)
    {
        int i=lo, j=hi;
        Point q=p[(lo+hi)/2];
        while (i<=j)
        {
            while (p[i].isLess(q)) i++;
            while (q.isLess(p[j])) j--;
            if (i<=j) exchange(i++, j--);
        }
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
    }

}   // end class GrahamScan