
from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize




class    _SCREAMING_SNAKE_CASE					( __UpperCamelCase	):
      _A  :						List[Any]      		=       1
      _A  :						List[str]      		=       2
      _A  :						Tuple      		=       3
      def __repr__(     self	):
          return F"""{self.__class__.__name__}.{self.name}"""





def 		SCREAMING_SNAKE_CASE__      ( __lowerCAmelCase      ,						__lowerCAmelCase      ,						__lowerCAmelCase							):
    snake_case__  ,   snake_case__  =			point
    return degrees(atana(y - miny      ,						x - minx							)							)





def 		SCREAMING_SNAKE_CASE__      ( __lowerCAmelCase      ,						__lowerCAmelCase      ,						__lowerCAmelCase							):
    snake_case__  ,   snake_case__  =			starting
    snake_case__  ,   snake_case__  =			via
    snake_case__  ,   snake_case__  =			target
    snake_case__  =			degrees(atana(ya - ya      ,						xa - xa							)							)
    via_angle %= 360
    snake_case__  =			degrees(atana(ya - ya      ,						xa - xa							)							)
    target_angle %= 360
    # t-
    #  \ \
    #   \ v
    #    \|
    #     s
    # via_angle is always lower than target_angle, if direction is left.
    # If they are same, it means they are on a same line of convex hull.
    if target_angle > via_angle:
        return Direction.left
    elif target_angle == via_angle:
        return Direction.straight
    else:
        return Direction.right





def 		SCREAMING_SNAKE_CASE__      ( __lowerCAmelCase							):

    if len(__lowerCAmelCase							) <= 2:
        # There is no convex hull
        raise ValueError("graham_scan: argument must contain more than 3 points."							)
    if len(__lowerCAmelCase							) == 3:
        return points
    # find the lowest and the most left point
    snake_case__  =			0
    snake_case__  ,   snake_case__  =			maxsize, maxsize
    for i, point in enumerate(__lowerCAmelCase							):
        snake_case__  =			point[0]
        snake_case__  =			point[1]
        if y < miny:
            snake_case__  =			y
            snake_case__  =			x
            snake_case__  =			i
        if y == miny and x < minx:
            snake_case__  =			x
            snake_case__  =			i

    # remove the lowest and the most left point from points for preparing for sort
    points.pop(__lowerCAmelCase							)

    snake_case__  =			sorted(__lowerCAmelCase      ,						key=lambda __lowerCAmelCase							: angle_comparer(__lowerCAmelCase      ,						__lowerCAmelCase      ,						__lowerCAmelCase							)							)
    # This insert actually costs complexity,
    # and you should instead add (minx, miny) into stack later.
    # I'm using insert just for easy understanding.
    sorted_points.insert(0      ,						(minx, miny)							)

    snake_case__  =			deque()
    stack.append(sorted_points[0]							)
    stack.append(sorted_points[1]							)
    stack.append(sorted_points[2]							)
    # In any ways, the first 3 points line are towards left.
    # Because we sort them the angle from minx, miny.
    snake_case__  =			Direction.left

    for i in range(3      ,						len(__lowerCAmelCase							)							):
        while True:
            snake_case__  =			stack[-2]
            snake_case__  =			stack[-1]
            snake_case__  =			sorted_points[i]
            snake_case__  =			check_direction(__lowerCAmelCase      ,						__lowerCAmelCase      ,						__lowerCAmelCase							)

            if next_direction == Direction.left:
                snake_case__  =			Direction.left
                break
            if next_direction == Direction.straight:
                if current_direction == Direction.left:
                    # We keep current_direction as left.
                    # Because if the straight line keeps as straight,
                    # we want to know if this straight line is towards left.
                    break
                elif current_direction == Direction.right:
                    # If the straight line is towards right,
                    # every previous points on those straigh line is not convex hull.
                    stack.pop()
            if next_direction == Direction.right:
                stack.pop()
        stack.append(sorted_points[i]							)
    return list(__lowerCAmelCase							)





def 		SCREAMING_SNAKE_CASE__      ( __lowerCAmelCase							):
    if len(__lowerCAmelCase							) > 1:
        snake_case__  =			len(__lowerCAmelCase							) // 2  # Finds the middle of the array
        snake_case__  =			arr[
            :middle_length
        ]  # Creates an array of the elements in the first half.
        snake_case__  =			arr[
            middle_length:
        ]  # Creates an array of the elements in the second half.
        snake_case__  =			len(__lowerCAmelCase							)
        snake_case__  =			len(__lowerCAmelCase							)
        merge(__lowerCAmelCase							)  # Starts sorting the left.
        merge(__lowerCAmelCase							)  # Starts sorting the right
        snake_case__  =			0  # Left Counter
        snake_case__  =			0  # Right Counter
        snake_case__  =			0  # Position Counter
        while (
            left_index < left_size and right_index < right_size
        ):  # Runs until the lowers size of the left and right are sorted.
            if left_array[left_index] < right_array[right_index]:
                snake_case__  =			left_array[left_index]
                left_index += 1
            else:
                snake_case__  =			right_array[right_index]
                right_index += 1
            index += 1
        while (
            left_index < left_size
        ):  # Adds the left over elements in the left half of the array
            snake_case__  =			left_array[left_index]
            left_index += 1
            index += 1
        while (
            right_index < right_size
        ):  # Adds the left over elements in the right half of the array
            snake_case__  =			right_array[right_index]
            right_index += 1
            index += 1
    return arr


if __name__ == "__main__":
     import doctest

     doctest.testmod()



