Jarvis and Graham

from functools import cmp_to_key

def read_file(file_path):
    points = []
    with open(file_path, 'r') as file:
        for line in file:
            coordinates = line.split(' ')
            x = int(coordinates[0])
            y = int(coordinates[1])
            points.append(Point(x, y))
    return points

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y


p0 = Point(0, 0)


# A utility function to find next to top in a stack
# Возвращает значение после вершины стека
def nextToTop(S):
    return S[-2]


# A utility function to return square of distance
# between p1 and p2
# Функция, возврящающая квадрат расстояния между p1 и p2
def distSq(p1, p2):
    return ((p1.x - p2.x) * (p1.x - p2.x) +
            (p1.y - p2.y) * (p1.y - p2.y))

# Функция, использующаяся функцией cmp_to_key, чтобы сортировать
# массив точек, относительно первой точки
def compare(p1, p2):
    o = orientation(p0, p1, p2)
    if o == 0:
        if distSq(p0, p2) >= distSq(p0, p1):
            return -1
        else:
            return 1
    else:
        if o == 2:
            return -1
        else:
            return 1

def left_index(points):
    minn = 0
    for i in range(1, len(points)):
        if points[i].x < points[minn].x:
            minn = i
        elif points[i].x == points[minn].x:
            if points[i].y < points[minn].y:
                minn = i
    return minn

def orientation(p, q, r):
    val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)

    if val == 0:
        return 0
    elif val > 0:
        return 1
    else:
        return 2

def convexHullJarvis(points, file_path):
    l = left_index(points)
    hull = []
    prev_p = l
    q = 0
    n = len(points)
    while (True):
        hull.append(prev_p)
        # Ищем точку q, такую чтобы угловой коэф между
        # (prev_p, i, q) был отрицательным и наименьшим
        q = (prev_p + 1) % n
        for i in range(n):
            if (orientation(points[prev_p],
                            points[i], points[q]) == 2):
                q = i
        prev_p = q
        if (prev_p == l):
            break
    with open(file_path, 'w') as file:
        for each in hull:
            file.write(str(points[each].x) + ' ' + str(points[each].y) + '\n')

def convexHullGraham(points, n, file_path):
    # Находим самую нижнюю точку
    ymin = points[0].y
    min = 0
    for i in range(1, n):
        y = points[i].y

        # Выбираем самую нижнюю точку либо
        # самую левую, если есть несколько самых нижних точек
        if ((y < ymin) or
                (ymin == y and points[i].x < points[min].x)):
            ymin = points[i].y
            min = i

    # Размещаем самую нижнюю точку на первую позицию
    points[0], points[min] = points[min], points[0]

    # Сортируем n - 1 точек, относительно первой точки
    # Точка p1 будет перед p2 если p2 имеет больший полярный угол
    # (в направлении против часовой стрелки), чем p1
    p0 = points[0]
    points = sorted(points, key=cmp_to_key(compare))

    # Если несколько точек имеют одинаковый угол с p0,
    # то удаляем все, кроме самой дальней от p0
    m = 1
    for i in range(1, n):

        # Продолжаем удалять i пока угол i и i + 1 такой же относительно p0
        while ((i < n - 1) and
               (orientation(p0, points[i], points[i + 1]) == 0)):
            i += 1

        points[m] = points[i]
        m += 1

    if m < 3:
        return

    # Создаем пустой стек и пушим в него первые три точки
    S = []
    S.append(points[0])
    S.append(points[1])
    S.append(points[2])

    for i in range(3, m):

        # Убираем вершину стека пока угол образованный nextToTop, top и points[i]
        # Совершает не левый поворот
        while ((len(S) > 1) and
               (orientation(nextToTop(S), S[-1], points[i]) != 2)):
            S.pop()
        S.append(points[i])

    with open(file_path, 'w') as file:
        while S:
            p = S[-1]
            file.write("(" + str(p.x) + ", " + str(p.y) + ")" + '\n')
            S.pop()

points_n = read_file('ConvexHullTask.txt')

#convexHullJarvis(points_n, 'ConvexHullRes.txt')

points = read_file('ConvexHullTask.txt')
n = len(points)
convexHullGraham(points, n, 'ConvexHullRes.txt')