


from __future__ import annotations

from collections.abc import Iterable






class        UpperCAmelCase__			:



    """simple docstring"""






    def __init__(     self   ,  A_   ,  A_       )    ->			List[Any]:
         __UpperCamelCase				, __UpperCamelCase       				=float(A_       ), float(A_       )






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






    def __ne__(     self   ,  A_       )    ->			List[str]:
         return not self == other






    def __gt__(     self   ,  A_       )    ->			List[Any]:
         if self.x > other.x:
              return True
         elif self.x == other.x:
              return self.y > other.y
         return False






    def __lt__(     self   ,  A_       )    ->			Any:
         return not self > other






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






    def __le__(     self   ,  A_       )    ->			Optional[Any]:
         if self.x < other.x:
              return True
         elif self.x == other.x:
              return self.y <= other.y
         return False






    def __repr__(     self       )    ->			Optional[int]:
         return f'({self.x}, {self.y})'






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

def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   list[Point] | list[list[float]] | Iterable[list[float]]     ,	):
     __UpperCamelCase       				=[]
     if list_of_tuples:
          for p in list_of_tuples:
               if isinstance(SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__							):
                    points.append(SCREAMING_SNAKE_CASE__							)
               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 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   list[Point] | list[list[float]]							):

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

     if not points:
          __UpperCamelCase       				=F'Expecting a list of points but got {points}'
          raise ValueError(SCREAMING_SNAKE_CASE__							)

     return _construct_points(SCREAMING_SNAKE_CASE__							)

def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   Point     ,	SCREAMING_SNAKE_CASE__     :   Point     ,	SCREAMING_SNAKE_CASE__     :   Point							):
     __UpperCamelCase       				=(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 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   list[Point]							):
     __UpperCamelCase       				=sorted(_validate_input(SCREAMING_SNAKE_CASE__							)							)
     __UpperCamelCase       				=len(SCREAMING_SNAKE_CASE__							)
     __UpperCamelCase       				=set()

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

                         if det_k > 0:
                              __UpperCamelCase       				=True
                         elif det_k < 0:
                              __UpperCamelCase       				=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]:
                                   __UpperCamelCase       				=False
                                   break

                    if points_left_of_ij and points_right_of_ij:
                         __UpperCamelCase       				=False
                         break

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

     return sorted(SCREAMING_SNAKE_CASE__							)

def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   list[Point]							):
     __UpperCamelCase       				=sorted(_validate_input(SCREAMING_SNAKE_CASE__							)							)
     __UpperCamelCase       				=len(SCREAMING_SNAKE_CASE__							)

     # 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

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

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

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

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

     _construct_hull(SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__							)
     _construct_hull(SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__							)

     return sorted(SCREAMING_SNAKE_CASE__							)

def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   list[Point]     ,	SCREAMING_SNAKE_CASE__     :   Point     ,	SCREAMING_SNAKE_CASE__     :   Point     ,	SCREAMING_SNAKE_CASE__     :   set[Point]							):
     if points:
          __UpperCamelCase       				=None
          __UpperCamelCase       				=float('-inf'							)
          __UpperCamelCase       				=[]

          for p in points:
               __UpperCamelCase       				=_det(SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__							)

               if det > 0:
                    candidate_points.append(SCREAMING_SNAKE_CASE__							)

                    if det > extreme_point_distance:
                         __UpperCamelCase       				=det
                         __UpperCamelCase       				=p

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

def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   list[Point]							):
     __UpperCamelCase       				=sorted(_validate_input(SCREAMING_SNAKE_CASE__							)							)
     __UpperCamelCase       				=len(SCREAMING_SNAKE_CASE__							)

     __UpperCamelCase       				=points[:2]
     for i in range(2     ,	SCREAMING_SNAKE_CASE__							):
          __UpperCamelCase       				=_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:
               __UpperCamelCase       				=points[i]
     i += 1

     for j in range(SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__							):
          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(SCREAMING_SNAKE_CASE__							) > 3 else convex_hull							)

def 		_UpperCAmelCase							(     ):
     __UpperCamelCase       				=[
         (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)]
     __UpperCamelCase       				=convex_hull_bf(SCREAMING_SNAKE_CASE__							)

     __UpperCamelCase       				=convex_hull_recursive(SCREAMING_SNAKE_CASE__							)
     assert results_bf == results_recursive

     __UpperCamelCase       				=convex_hull_melkman(SCREAMING_SNAKE_CASE__							)
     assert results_bf == results_melkman

     print(SCREAMING_SNAKE_CASE__							)


if __name__ == "__main__":
   main()









def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   Union[str, Any]     ,	SCREAMING_SNAKE_CASE__     :   int							):
     if n < 0:
          return 0
     # table[i] represents the number of ways to get to amount i
     __UpperCamelCase       				=[0] * (n + 1)

     # There is exactly 1 way to get to zero(You pick no coins).
     __UpperCamelCase       				=1

     # Pick all coins one by one and update table[] values
     # after the index greater than or equal to the value of the
     # picked coin
     for coin_val in s:
          for j in range(SCREAMING_SNAKE_CASE__     ,	n + 1							):
               table[j] += table[j - coin_val]

     return table[n]


if __name__ == "__main__":
   import doctest

   doctest.testmod()





