package project;
import java.util.Stack;

public class Main
{
    static int rootX,rootY;
    public static void main(String[] args)
    {
        //int[] newX = {15,30,40,20,10};
        //int[] newY = {60,50,20,20,10};
        int[] newX = {400,800,1000,500,400,200};
        int[] newY = {100,100,300,300,500,300};
        int size = 6;
        
        int x = newX[0];
        int y = newY[0];
        for (int i = 0; i < size; i++) //знаходимо точку з найменшою y-координатою
        {
            if (y > newY[i] || (y == newY[i] && x > newX[i]))
            {
                x = newX[i];
                y = newY[i];
            }
        }
        rootX = x;
        rootY = y;
        System.out.println(x +" "+ y);
        int rootPosition = elementPositionInArray(newX, newY, size, rootX, rootY);// визначаємо позицію цієї точки
        changePlaces(newX, newY, 0, rootPosition);//ставимо цю точку на початок
        sortArray(newX, newY, size);
        System.out.println("After sort: ");
        for(int i = 0; i < size; ++i)
        {
            System.out.println("x = " + newX[i] + " y = " + newY[i]);
        }
        Stack<Integer> X = new Stack<>();
        Stack<Integer> Y = new Stack<>();
        for(int i = 0; i < 3; ++i)
        {
            X.add(newX[i]);
            Y.add(newY[i]);
        }
        for (int i = 3; i < size; ++i) //алгоритм Грехема
        {
            while (pointOrder(NextToTop(X), X.peek(), newX[i], NextToTop(Y), Y.peek(), newY[i]) != 2)
            {
                X.pop();
                Y.pop();
            }
            X.add(newX[i]);
            Y.add(newY[i]);
        }
        System.out.println("End: ");
        for(int i = 0; i < size; ++i)
        {
            //System.out.println("x = " + newX[i] + " y = " + newY[i]);
            System.out.println("x = " + X.get(i) + " y = " + Y.get(i));
        }
    }
    private static int NextToTop(Stack<Integer> S)
    {

    }
    public static void sortArray(int[] newX, int[] newY, int size)
    {
        for (int i = 1; i < size; ++i)
        {
            for (int y = i + 1; y < size; ++y)
            {
                int point1X = newX[i];
                int point1Y = newY[i];
                int point2X = newX[y];
                int point2Y = newY[y];
                int order = pointOrder(rootX, point1X, point2X,rootY, point1Y, point2Y);
                if (order == 0)
                {
                    if (distance(rootX, point2X, rootY, point2Y) <= distance(rootX, point1X, rootY, point1Y))
                    {
                        changePlaces(newX,newY, i, y);
                    }
                }
                else if (order == 1)
                {
                    changePlaces(newX,newY, i, y);
                }
            }
        }
    }
    public static int pointOrder(int point1X, int point2X, int point3X, int point1Y, int point2Y, int point3Y)
    {
        int area = (point2Y - point1Y) * (point3X - point2X) - (point2X - point1X) * (point3Y - point2Y);
        if (area > 0)
            return 1;
        else if (area < 0)
            return 2;
        return 0;
    }
    // знаходимо відстань між двома точками
    public static int distance(int point1X, int point2X, int point1Y, int point2Y)
    {
        int xLength = point1X - point2X;
        int yLength = point1Y - point2Y;
        return xLength * xLength + yLength * yLength;
    }
    public static void changePlaces(int[] newX, int[] newY, int positionA, int positionB)
    {
        int tmpX = newX[positionA];
        int tmpY = newY[positionA];
        newX[positionA] = newX[positionB];
        newY[positionA] = newY[positionB];
        newX[positionB] = tmpX;
        newY[positionB] = tmpY;
    }
    public static int elementPositionInArray(int[] newX, int[] newY, int size, int x, int y)
    {
        for (int i = 0; i < size; ++i)
        {
            if (newX[i] == x && newY[i] == y)
            {
                return i;
            }
        }
        return -1;
    }
}