public class Check {
    public ArrayList<Point> quickHull(ArrayList<Point> points){
        System.out.println("Зашли в Check?");
        ArrayList<Point> qHull=new ArrayList<Point>();
        int min=Integer.MAX_VALUE;
        int max= Integer.MIN_VALUE;
        int imin=points.size()-1;int imax= points.size()-1;
        for(int i=0;i<points.size();i++){
            if (points.get(i).x>min){
                min=points.get(i).x;
                imin=i;
            }
            if (points.get(i).x>max){
                max=points.get(i).x;
                imax=i;
            }
        }
        Point A= points.get(imin);
        Point B=points.get(imax);
       qHull.add(A);
       qHull.add(B);
        points.remove(A);
        points.remove(B);

        //Создаём левое и правое относительно AB множества точек
        ArrayList<Point> leftSet=new ArrayList<Point>();
        ArrayList<Point> rightSet=new ArrayList<Point>();

        //Разбиваем множества точек на левое и правое множество

        for (int i=0;i<points.size();i++){
            Point p=points.get(i);
            if (isLeft(A,B,p)==1){
                leftSet.add(points.get(i));
            }
            else rightSet.add(p);
        }
        hullSet(A,B,leftSet,qHull);
        hullSet(B,A,rightSet,qHull);
        return qHull;
    }
    public int isLeft(Point A,Point B,Point P)
    {
        long cross=((B.x-A.x)*(P.y-A.y)-(B.y-A.y)*(P.x-A.x));
        return (cross>0)?1:-1;
    }
    public long distance(Point A, Point B,Point P)
    {
        long num=((B.x-A.x)*(P.y-A.y)-(B.y-A.y)*(P.x-A.x));
        if (num<0){
            num=-num;
        }
        return num;
    }
    public void hullSet(Point A, Point B, ArrayList<Point> set, ArrayList<Point> hull){
        int insertPosition=set.indexOf(B);
        if (set.size()==0){
            return;
        }
        if (set.size()==1){
            Point p=set.get(0);
            set.remove(p);
            hull.add(insertPosition,p);
            return;
        }
        long dist=Integer.MIN_VALUE;
        int furtherPoint=0;
        for(int i=0;i<set.size();i++){
            Point p=set.get(i);
            long distance=distance(A,B,p);
            if(distance(A,B,p)>dist)
            {
                dist=distance;
                furtherPoint=i;
            }
        }
        Point P=set.get(furtherPoint);
        set.remove(furtherPoint);
        hull.add(insertPosition,P);

        //Определяем кто находится слева от AP

        ArrayList<Point> leftSetAP=  new ArrayList<Point>();
         for(int i=0;i<set.size();i++){
             Point M=set.get(i);
             if (isLeft(A,B,M)==1){
                 leftSetAP.add(M);
             }
         }

        //Определяем кто находится слева от PB

        ArrayList<Point> leftSetPB=new ArrayList<Point>();
        for(int i=0;i<set.size();i++){
            Point M=set.get(i);
            if (isLeft(P,B,M)==1){
                leftSetPB.add(M);
            }
        }
        hullSet(A,P,leftSetAP,hull);
        hullSet(P,B,leftSetPB,hull);

    }
}