

from __future__ import annotations

from collections.abc import Iterable





class A__     :



 """simple docstring"""







 def __init__(		self			:						Optional[int]  ,    A_			:						Dict  ,    A_			:						Optional[int]							):






      '''simple docstring'''




      _lowerCAmelCase   ,      _lowerCAmelCase :       Union[str, Any]	   =     float(A_							), float(A_							)

 def __eq__(		self			:						Any  ,    A_			:						str							):






      '''simple docstring'''




      return self.x == other.x and self.y == other.y

 def __ne__(		self			:						List[Any]  ,    A_			:						Dict							):






      '''simple docstring'''




      return not self == other

 def __gt__(		self			:						Union[str, Any]  ,    A_			:						Union[str, Any]							):






      '''simple docstring'''




      if self.x > other.x:
           return True
      elif self.x == other.x:
           return self.y > other.y
      return False

 def __lt__(		self			:						Union[str, Any]  ,    A_			:						List[Any]							):






      '''simple docstring'''




      return not self > other

 def __ge__(		self			:						List[str]  ,    A_			:						Tuple							):






      '''simple docstring'''




      if self.x > other.x:
           return True
      elif self.x == other.x:
           return self.y >= other.y
      return False

 def __le__(		self			:						Dict  ,    A_			:						Union[str, Any]							):






      '''simple docstring'''




      if self.x < other.x:
           return True
      elif self.x == other.x:
           return self.y <= other.y
      return False

 def __repr__(		self			:						Union[str, Any]							):






      '''simple docstring'''




      return F'''({self.x}, {self.y})'''


 def __hash__(		self			:						List[str]							):






      '''simple docstring'''




      return hash(self.x							)







def 						_snake_case		(     SCREAMING_SNAKE_CASE		,				)							->   list[Point]:

     """simple docstring"""







     _lowerCAmelCase :       list[Point]	   =     []
     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 						_snake_case		(     SCREAMING_SNAKE_CASE					)							->   list[Point]:

     """simple docstring"""







     if not hasattr(SCREAMING_SNAKE_CASE		,				"__iter__"					):
          _lowerCAmelCase :       str	   =     f'''Expecting an iterable object but got an non-iterable type {points}'''
          raise ValueError(SCREAMING_SNAKE_CASE					)

     if not points:
          _lowerCAmelCase :       Tuple	   =     f'''Expecting a list of points but got {points}'''
          raise ValueError(SCREAMING_SNAKE_CASE					)

     return _construct_points(SCREAMING_SNAKE_CASE					)







def 						_snake_case		(     SCREAMING_SNAKE_CASE		,				SCREAMING_SNAKE_CASE		,				SCREAMING_SNAKE_CASE					)							->   float:

     """simple docstring"""







     _lowerCAmelCase :       str	   =     (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 						_snake_case		(     SCREAMING_SNAKE_CASE					)							->   list[Point]:

     """simple docstring"""







     _lowerCAmelCase :       Union[str, Any]	   =     sorted(_validate_input(SCREAMING_SNAKE_CASE					)					)
     _lowerCAmelCase :       List[str]	   =     len(SCREAMING_SNAKE_CASE					)
     _lowerCAmelCase :       Tuple	   =     set()

     for i in range(n - 1					):
          for j in range(i + 1		,				SCREAMING_SNAKE_CASE					):
               _lowerCAmelCase :       List[Any]	   =     False
               _lowerCAmelCase :       Optional[Any]	   =     True
               for k in range(SCREAMING_SNAKE_CASE					):
                    if k != i and k != j:
                         _lowerCAmelCase :       int	   =     _det(points[i]		,				points[j]		,				points[k]					)

                         if det_k > 0:
                              _lowerCAmelCase :       Tuple	   =     True
                         elif det_k < 0:
                              _lowerCAmelCase :       Any	   =     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]:
                                   _lowerCAmelCase :       List[Any]	   =     False
                                   break

                    if points_left_of_ij and points_right_of_ij:
                         _lowerCAmelCase :       Union[str, Any]	   =     False
                         break

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

     return sorted(SCREAMING_SNAKE_CASE					)







def 						_snake_case		(     SCREAMING_SNAKE_CASE					)							->   list[Point]:

     """simple docstring"""







     _lowerCAmelCase :       Any	   =     sorted(_validate_input(SCREAMING_SNAKE_CASE					)					)
     _lowerCAmelCase :       List[Any]	   =     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

     _lowerCAmelCase :       Optional[int]	   =     points[0]
     _lowerCAmelCase :       str	   =     points[n - 1]

     _lowerCAmelCase :       Optional[Any]	   =     {left_most_point, right_most_point}
     _lowerCAmelCase :       Optional[Any]	   =     []
     _lowerCAmelCase :       List[Any]	   =     []

     for i in range(1		,				n - 1					):
          _lowerCAmelCase :       int	   =     _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 						_snake_case		(     SCREAMING_SNAKE_CASE		,				SCREAMING_SNAKE_CASE		,				SCREAMING_SNAKE_CASE		,				SCREAMING_SNAKE_CASE					)							->   None:

     """simple docstring"""







     if points:
          _lowerCAmelCase :       Dict	   =     None
          _lowerCAmelCase :       Optional[Any]	   =     float("-inf"					)
          _lowerCAmelCase :       Tuple	   =     []

          for p in points:
               _lowerCAmelCase :       Optional[int]	   =     _det(SCREAMING_SNAKE_CASE		,				SCREAMING_SNAKE_CASE		,				SCREAMING_SNAKE_CASE					)

               if det > 0:
                    candidate_points.append(SCREAMING_SNAKE_CASE					)

                    if det > extreme_point_distance:
                         _lowerCAmelCase :       Optional[Any]	   =     det
                         _lowerCAmelCase :       Any	   =     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 						_snake_case		(     SCREAMING_SNAKE_CASE					)							->   list[Point]:

     """simple docstring"""







     _lowerCAmelCase :       Optional[int]	   =     sorted(_validate_input(SCREAMING_SNAKE_CASE					)					)
     _lowerCAmelCase :       Union[str, Any]	   =     len(SCREAMING_SNAKE_CASE					)

     _lowerCAmelCase :       Optional[int]	   =     points[:2]
     for i in range(2		,				SCREAMING_SNAKE_CASE					):
          _lowerCAmelCase :       str	   =     _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:
               _lowerCAmelCase :       Any	   =     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 						_snake_case		(     )							->   Any:

     """simple docstring"""







     _lowerCAmelCase :       Optional[Any]	   =     [
         (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)]
     _lowerCAmelCase :       int	   =     convex_hull_bf(SCREAMING_SNAKE_CASE					)

     _lowerCAmelCase :       Optional[int]	   =     convex_hull_recursive(SCREAMING_SNAKE_CASE					)
     assert results_bf == results_recursive

     _lowerCAmelCase :       Dict	   =     convex_hull_melkman(SCREAMING_SNAKE_CASE					)
     assert results_bf == results_melkman

     print(SCREAMING_SNAKE_CASE					)


if __name__ == "__main__":
  main()









def 						_snake_case		(     SCREAMING_SNAKE_CASE		,				SCREAMING_SNAKE_CASE		,				SCREAMING_SNAKE_CASE					)							->   Optional[int]:

     """simple docstring"""







     if power < 0:
          return -1
     base %= mod
     _lowerCAmelCase :       Tuple	   =     1

     while power > 0:
          if power & 1:
               _lowerCAmelCase :       Optional[Any]	   =     (result * base) % mod
          _lowerCAmelCase :       int	   =     power >> 1
          _lowerCAmelCase :       Optional[int]	   =     (base * base) % mod

     return result







def 						_snake_case		(     )							->   Optional[int]:

     """simple docstring"""







     print(modular_exponential(3		,				200		,				13					)					)


if __name__ == "__main__":
  import doctest

  doctest.testmod()

  main()






