





from __future__ import annotations

from collections.abc import Iterable





class A_   :




   def __init__(self      :Union[str, Any]       ,  _UpperCamelCase      :Any       ,  _UpperCamelCase      :Tuple					)->   Optional[int]:
         __A  ,		__A			  =							float(_UpperCamelCase					), float(_UpperCamelCase					)




   def __eq__(self      :Union[str, Any]       ,  _UpperCamelCase      :List[Any]					)->   Optional[Any]:
         return self.x == other.x and self.y == other.y




   def __ne__(self      :Optional[Any]       ,  _UpperCamelCase      :str					)->   Any:
         return not self == other




   def __gt__(self      :Optional[int]       ,  _UpperCamelCase      :Tuple					)->   str:
         if self.x > other.x:
               return True
         elif self.x == other.x:
               return self.y > other.y
         return False




   def __lt__(self      :Optional[int]       ,  _UpperCamelCase      :List[str]					)->   Tuple:
         return not self > other




   def __ge__(self      :Tuple       ,  _UpperCamelCase      :Optional[Any]					)->   List[Any]:
         if self.x > other.x:
               return True
         elif self.x == other.x:
               return self.y >= other.y
         return False




   def __le__(self      :str       ,  _UpperCamelCase      :Union[str, Any]					)->   Dict:
         if self.x < other.x:
               return True
         elif self.x == other.x:
               return self.y <= other.y
         return False




   def __repr__(self      :int					)->   List[str]:
         return f"""({self.x}, {self.y})"""






   def __hash__(self      :List[Any]					)->   Any:
         return hash(self.x					)





def _a							(      lowerCamelCase:  list[Point] | list[list[float]] | Iterable[list[float]]   ,							)      ->		list[Point]:







      '''simple docstring'''






      __A			  =							[]
      if list_of_tuples:
            for p in list_of_tuples:
                  if isinstance(lowerCamelCase   ,							lowerCamelCase					):
                        points.append(lowerCamelCase					)
                  else:
                        try:
                              points.append(Point(p[0]   ,							p[1]					)					)
                        except (IndexError, TypeError):
                              print(
                                  F"""Ignoring deformed point {p}. All points"""
                                  ''' must have at least 2 coordinates.'''					)
      return points



def _a							(      lowerCamelCase:  list[Point] | list[list[float]]					)      ->		list[Point]:







      '''simple docstring'''






      if not hasattr(lowerCamelCase   ,							'''__iter__'''					):
            __A			  =							F"""Expecting an iterable object but got an non-iterable type {points}"""
            raise ValueError(lowerCamelCase					)

      if not points:
            __A			  =							F"""Expecting a list of points but got {points}"""
            raise ValueError(lowerCamelCase					)

      return _construct_points(lowerCamelCase					)



def _a							(      lowerCamelCase:  Point   ,							lowerCamelCase:  Point   ,							lowerCamelCase:  Point					)      ->		float:







      '''simple docstring'''






      __A			  =							(a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x)
      return det



def _a							(      lowerCamelCase:  list[Point]					)      ->		list[Point]:







      '''simple docstring'''






      __A			  =							sorted(_validate_input(lowerCamelCase					)					)
      __A			  =							len(lowerCamelCase					)
      __A			  =							set()

      for i in range(n - 1					):
            for j in range(i + 1   ,							lowerCamelCase					):
                  __A			  =							__A			  =							False
                  __A			  =							True
                  for k in range(lowerCamelCase					):
                        if k != i and k != j:
                              __A			  =							_det(points[i]   ,							points[j]   ,							points[k]					)

                              if det_k > 0:
                                    __A			  =							True
                              elif det_k < 0:
                                    __A			  =							True
                              else:
                                    # point[i], point[j], point[k] all lie on a straight line
                                    # if point[k] is to the left of point[i] or it's to the
                                    # right of point[j], then point[i], point[j] cannot be
                                    # part of the convex hull of A
                                    if points[k] < points[i] or points[k] > points[j]:
                                          __A			  =							False
                                          break

                        if points_left_of_ij and points_right_of_ij:
                              __A			  =							False
                              break

                  if ij_part_of_convex_hull:
                        convex_set.update([points[i], points[j]]					)

      return sorted(lowerCamelCase					)



def _a							(      lowerCamelCase:  list[Point]					)      ->		list[Point]:







      '''simple docstring'''






      __A			  =							sorted(_validate_input(lowerCamelCase					)					)
      __A			  =							len(lowerCamelCase					)

      # divide all the points into an upper hull and a lower hull
      # the left most point and the right most point are definitely
      # members of the convex hull by definition.
      # use these two anchors to divide all the points into two hulls,
      # an upper hull and a lower hull.

      # all points to the left (above) the line joining the extreme points belong to the
      # upper hull
      # all points to the right (below) the line joining the extreme points below to the
      # lower hull
      # ignore all points on the line joining the extreme points since they cannot be
      # part of the convex hull

      __A			  =							points[0]
      __A			  =							points[n - 1]

      __A			  =							{left_most_point, right_most_point}
      __A			  =							[]
      __A			  =							[]

      for i in range(1   ,							n - 1					):
            __A			  =							_det(lowerCamelCase   ,							lowerCamelCase   ,							points[i]					)

            if det > 0:
                  upper_hull.append(points[i]					)
            elif det < 0:
                  lower_hull.append(points[i]					)

      _construct_hull(lowerCamelCase   ,							lowerCamelCase   ,							lowerCamelCase   ,							lowerCamelCase					)
      _construct_hull(lowerCamelCase   ,							lowerCamelCase   ,							lowerCamelCase   ,							lowerCamelCase					)

      return sorted(lowerCamelCase					)



def _a							(      lowerCamelCase:  list[Point]   ,							lowerCamelCase:  Point   ,							lowerCamelCase:  Point   ,							lowerCamelCase:  set[Point]					)      ->		None:







      '''simple docstring'''






      if points:
            __A			  =							None
            __A			  =							float('''-inf'''					)
            __A			  =							[]

            for p in points:
                  __A			  =							_det(lowerCamelCase   ,							lowerCamelCase   ,							lowerCamelCase					)

                  if det > 0:
                        candidate_points.append(lowerCamelCase					)

                        if det > extreme_point_distance:
                              __A			  =							det
                              __A			  =							p

            if extreme_point:
                  _construct_hull(lowerCamelCase   ,							lowerCamelCase   ,							lowerCamelCase   ,							lowerCamelCase					)
                  convex_set.add(lowerCamelCase					)
                  _construct_hull(lowerCamelCase   ,							lowerCamelCase   ,							lowerCamelCase   ,							lowerCamelCase					)



def _a							(      lowerCamelCase:  list[Point]					)      ->		list[Point]:







      '''simple docstring'''






      __A			  =							sorted(_validate_input(lowerCamelCase					)					)
      __A			  =							len(lowerCamelCase					)

      __A			  =							points[:2]
      for i in range(2   ,							lowerCamelCase					):
            __A			  =							_det(convex_hull[1]   ,							convex_hull[0]   ,							points[i]					)
            if det > 0:
                  convex_hull.insert(0   ,							points[i]					)
                  break
            elif det < 0:
                  convex_hull.append(points[i]					)
                  break
            else:
                  __A			  =							points[i]
      i += 1

      for j in range(lowerCamelCase   ,							lowerCamelCase					):
            if (
                _det(convex_hull[0]   ,							convex_hull[-1]   ,							points[j]					) > 0
                and _det(convex_hull[-1]   ,							convex_hull[0]   ,							points[1]					) < 0
            ):
                  # The point lies within the convex hull
                  continue

            convex_hull.insert(0   ,							points[j]					)
            convex_hull.append(points[j]					)
            while _det(convex_hull[0]   ,							convex_hull[1]   ,							convex_hull[2]					) >= 0:
                  del convex_hull[1]
            while _det(convex_hull[-1]   ,							convex_hull[-2]   ,							convex_hull[-3]					) <= 0:
                  del convex_hull[-2]

    # `convex_hull` is contains the convex hull in circular order
      return sorted(convex_hull[1:] if len(lowerCamelCase					) > 3 else convex_hull					)



def _a							(      )      ->		int:







      '''simple docstring'''






      __A			  =							[
          (0, 3),
          (2, 2),
          (1, 1),
          (2, 1),
          (3, 0),
          (0, 0),
          (3, 3),
          (2, -1),
          (2, -4),
          (1, -3),
      ]
      # the convex set of points is
      # [(0, 0), (0, 3), (1, -3), (2, -4), (3, 0), (3, 3)]
      __A			  =							convex_hull_bf(lowerCamelCase					)

      __A			  =							convex_hull_recursive(lowerCamelCase					)
      assert results_bf == results_recursive

      __A			  =							convex_hull_melkman(lowerCamelCase					)
      assert results_bf == results_melkman

      print(lowerCamelCase					)


if __name__ == "__main__":
       main()












def _a							(      lowerCamelCase:  List[Any]					)      ->		Optional[Any]:







      '''simple docstring'''






      __A			  =							[7_01, 3_01, 1_32, 57, 23, 10, 4, 1]
      for gap in gaps:
            for i in range(lowerCamelCase   ,							len(lowerCamelCase					)					):
                  __A			  =							collection[i]
                  __A			  =							i
                  while j >= gap and collection[j - gap] > insert_value:
                        __A			  =							collection[j - gap]
                        j -= gap
                  if j != i:
                        __A			  =							insert_value
      return collection


if __name__ == "__main__":
       from doctest import testmod

       testmod()
       snake_case__   :				Optional[int]						=	input('Enter numbers separated by a comma:\n').strip()
       snake_case__   :				int						=	[int(item) for item in user_input.split(',')]
       print(shell_sort(unsorted))





