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;
}
}
