

from __future__ import annotations

from collections.abc import Iterable



class     lowercase_       :



      def __init__(     self :							Optional[int]     ,   A__ :							Optional[Any]     ,   A__ :							Optional[Any]						)       ->	int:
        _snake_case,	_snake_case		=				float(A__						), float(A__						)



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



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



      def __gt__(     self :							str     ,   A__ :							str						)       ->	int:
        if self.x > other.x:
          return True
        elif self.x == other.x:
          return self.y > other.y
        return False



      def __lt__(     self :							Optional[int]     ,   A__ :							Optional[int]						)       ->	List[Any]:
        return not self > other



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



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



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







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



def  snake_case_(_UpperCamelCase					,			)				->      list[Point]:



  """simple docstring"""






  _snake_case		=				[]
  if list_of_tuples:
    for p in list_of_tuples:
      if isinstance(_UpperCamelCase					,			_UpperCamelCase	):
        points.append(_UpperCamelCase	)
      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_(_UpperCamelCase	)				->      list[Point]:



  """simple docstring"""






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

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

  return _construct_points(_UpperCamelCase	)



def  snake_case_(_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase	)				->      float:



  """simple docstring"""






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



  """simple docstring"""






  _snake_case		=				sorted(_validate_input(_UpperCamelCase	)	)
  _snake_case		=				len(_UpperCamelCase	)
  _snake_case		=				set()

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

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

        if points_left_of_ij and points_right_of_ij:
          _snake_case		=				False
          break

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

  return sorted(_UpperCamelCase	)



def  snake_case_(_UpperCamelCase	)				->      list[Point]:



  """simple docstring"""






  _snake_case		=				sorted(_validate_input(_UpperCamelCase	)	)
  _snake_case		=				len(_UpperCamelCase	)

  # 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

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

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

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

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

  _construct_hull(_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase	)
  _construct_hull(_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase	)

  return sorted(_UpperCamelCase	)



def  snake_case_(_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase	)				->      None:



  """simple docstring"""






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

    for p in points:
      _snake_case		=				_det(_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase	)

      if det > 0:
        candidate_points.append(_UpperCamelCase	)

        if det > extreme_point_distance:
          _snake_case		=				det
          _snake_case		=				p

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



def  snake_case_(_UpperCamelCase	)				->      list[Point]:



  """simple docstring"""






  _snake_case		=				sorted(_validate_input(_UpperCamelCase	)	)
  _snake_case		=				len(_UpperCamelCase	)

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

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



def  snake_case_()				->      List[Any]:



  """simple docstring"""






  _snake_case		=				[
      (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)]
  _snake_case		=				convex_hull_bf(_UpperCamelCase	)

  _snake_case		=				convex_hull_recursive(_UpperCamelCase	)
  assert results_bf == results_recursive

  _snake_case		=				convex_hull_melkman(_UpperCamelCase	)
  assert results_bf == results_melkman

  print(_UpperCamelCase	)


if __name__ == "__main__":
 main()




import functools
from math import sqrt
from time import time



def  snake_case_(_UpperCamelCase					,			*_UpperCamelCase					,			**_UpperCamelCase	)				->      str:



  """simple docstring"""






  _snake_case		=				time()
  _snake_case		=				func(*_UpperCamelCase					,			**_UpperCamelCase	)
  _snake_case		=				time()
  if int(end - start	) > 0:
    print(F"""{func.__name__} runtime: {(end - start):0.4f} s"""	)
  else:
    print(F"""{func.__name__} runtime: {(end - start) * 1_000:0.4f} ms"""	)
  return output



def  snake_case_(_UpperCamelCase	)				->      list[int]:



  """simple docstring"""






  if n < 0:
    raise Exception('''n is negative'''	)
  if n == 0:
    return [0]
  _snake_case		=				[0, 1]
  for _ in range(n - 1	):
    fib.append(fib[-1] + fib[-2]	)
  return fib



def  snake_case_(_UpperCamelCase	)				->      list[int]:



  """simple docstring"""






  def fib_recursive_term(_UpperCamelCase	) -> int:
    if i < 0:
      raise Exception('''n is negative'''	)
    if i < 2:
      return i
    return fib_recursive_term(i - 1	) + fib_recursive_term(i - 2	)

  if n < 0:
    raise Exception('''n is negative'''	)
  return [fib_recursive_term(_UpperCamelCase	) for i in range(n + 1	)]



def  snake_case_(_UpperCamelCase	)				->      list[int]:



  """simple docstring"""






  @functools.cache
  def fib_recursive_term(_UpperCamelCase	) -> int:
    if i < 0:
      raise Exception('''n is negative'''	)
    if i < 2:
      return i
    return fib_recursive_term(i - 1	) + fib_recursive_term(i - 2	)

  if n < 0:
    raise Exception('''n is negative'''	)
  return [fib_recursive_term(_UpperCamelCase	) for i in range(n + 1	)]



def  snake_case_(_UpperCamelCase	)				->      list[int]:



  """simple docstring"""






  if n < 0:
    raise Exception('''n is negative'''	)
  # Cache must be outside recursuive function
  # other it will reset every time it calls itself.
  _snake_case		=				{0: 0, 1: 1, 2: 1}  # Prefilled cache

  def rec_fn_memoized(_UpperCamelCase	) -> int:
    if num in cache:
      return cache[num]

    _snake_case		=				rec_fn_memoized(num - 1	) + rec_fn_memoized(num - 2	)
    _snake_case		=				value
    return value

  return [rec_fn_memoized(_UpperCamelCase	) for i in range(n + 1	)]



def  snake_case_(_UpperCamelCase	)				->      list[int]:



  """simple docstring"""






  if n < 0:
    raise Exception('''n is negative'''	)
  if n >= 1_475:
    raise Exception('''n is too large'''	)
  _snake_case		=				sqrt(5	)
  _snake_case		=				(1 + sqrt_a) / 2
  return [round(phi**i / sqrt_a	) for i in range(n + 1	)]


if __name__ == "__main__":
 __A     						=      30
 time_func(fib_iterative, num)
 time_func(fib_recursive, num)  # Around 3s runtime
 time_func(fib_recursive_cached, num)  # Around 0ms runtime
 time_func(fib_memoization, num)
 time_func(fib_binet, num)

