


from __future__ import annotations

from collections.abc import Iterable




class A  :






      def __init__( self						:					List[Any]      ,       lowercase_						:					int      ,       lowercase_						:					Optional[Any]			) ->						Union[str, Any]:
             """simple docstring"""




             _lowerCamelCase     ,					_lowerCamelCase	:		List[str]          =float(lowercase_			), float(lowercase_			)






      def __eq__( self						:					Optional[Any]      ,       lowercase_						:					Optional[Any]			) ->						Optional[Any]:
             """simple docstring"""




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






      def __ne__( self						:					Union[str, Any]      ,       lowercase_						:					Dict			) ->						Tuple:
             """simple docstring"""




             return not self == other






      def __gt__( self						:					List[Any]      ,       lowercase_						:					int			) ->						Dict:
             """simple docstring"""




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






      def __lt__( self						:					Tuple      ,       lowercase_						:					str			) ->						Optional[Any]:
             """simple docstring"""




             return not self > other






      def __ge__( self						:					Union[str, Any]      ,       lowercase_						:					Any			) ->						Optional[int]:
             """simple docstring"""




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






      def __le__( self						:					Any      ,       lowercase_						:					str			) ->						Dict:
             """simple docstring"""




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






      def __repr__( self						:					str			) ->						str:
             """simple docstring"""




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






      def __hash__( self						:					Dict			) ->						List[str]:
             """simple docstring"""




             return hash(self.x			)




def      a_				(   SCREAMING_SNAKE_CASE__ :				list[Point] | list[list[float]] | Iterable[list[float]]		,      ):
       '''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      a_				(   SCREAMING_SNAKE_CASE__ :				list[Point] | list[list[float]]					):
       '''simple docstring'''





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

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

       return _construct_points(SCREAMING_SNAKE_CASE__					)




def      a_				(   SCREAMING_SNAKE_CASE__ :				Point		,      SCREAMING_SNAKE_CASE__ :				Point		,      SCREAMING_SNAKE_CASE__ :				Point					):
       '''simple docstring'''





       _lowerCamelCase	:		Optional[Any]          =(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_				(   SCREAMING_SNAKE_CASE__ :				list[Point]					):
       '''simple docstring'''





       _lowerCamelCase	:		Dict          =sorted(_validate_input(SCREAMING_SNAKE_CASE__					)					)
       _lowerCamelCase	:		Tuple          =len(SCREAMING_SNAKE_CASE__					)
       _lowerCamelCase	:		List[str]          =set()

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

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

                            if points_left_of_ij and points_right_of_ij:
                                   _lowerCamelCase	:		int          =False
                                   break

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

       return sorted(SCREAMING_SNAKE_CASE__					)




def      a_				(   SCREAMING_SNAKE_CASE__ :				list[Point]					):
       '''simple docstring'''





       _lowerCamelCase	:		Any          =sorted(_validate_input(SCREAMING_SNAKE_CASE__					)					)
       _lowerCamelCase	:		str          =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	:		Tuple          =points[0]
       _lowerCamelCase	:		Tuple          =points[n - 1]

       _lowerCamelCase	:		Union[str, Any]          ={left_most_point, right_most_point}
       _lowerCamelCase	:		List[Any]          =[]
       _lowerCamelCase	:		Optional[int]          =[]

       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      a_				(   SCREAMING_SNAKE_CASE__ :				list[Point]		,      SCREAMING_SNAKE_CASE__ :				Point		,      SCREAMING_SNAKE_CASE__ :				Point		,      SCREAMING_SNAKE_CASE__ :				set[Point]					):
       '''simple docstring'''





       if points:
              _lowerCamelCase	:		Any          =None
              _lowerCamelCase	:		int          =float('-inf'					)
              _lowerCamelCase	:		Any          =[]

              for p in points:
                     _lowerCamelCase	:		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	:		List[str]          =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      a_				(   SCREAMING_SNAKE_CASE__ :				list[Point]					):
       '''simple docstring'''





       _lowerCamelCase	:		int          =sorted(_validate_input(SCREAMING_SNAKE_CASE__					)					)
       _lowerCamelCase	:		Tuple          =len(SCREAMING_SNAKE_CASE__					)

       _lowerCamelCase	:		Tuple          =points[:2]
       for i in range(2		,      SCREAMING_SNAKE_CASE__					):
              _lowerCamelCase	:		Optional[Any]          =_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	:		Dict          =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      a_				(   ):
       '''simple docstring'''





       _lowerCamelCase	:		Union[str, 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	:		List[Any]          =convex_hull_bf(SCREAMING_SNAKE_CASE__					)

       _lowerCamelCase	:		Dict          =convex_hull_recursive(SCREAMING_SNAKE_CASE__					)
       assert results_bf == results_recursive

       _lowerCamelCase	:		int          =convex_hull_melkman(SCREAMING_SNAKE_CASE__					)
       assert results_bf == results_melkman

       print(SCREAMING_SNAKE_CASE__					)


if __name__ == "__main__":
 main()






from __future__ import annotations

from abc import abstractmethod
from collections.abc import Iterable
from typing import Generic, Protocol, TypeVar




class A  (       UpperCamelCase_					):






      @abstractmethod
      def __lt__( self						:					T      ,       lowercase_						:					T			) ->						bool:
             """simple docstring"""




             pass






      @abstractmethod
      def __gt__( self						:					T      ,       lowercase_						:					T			) ->						bool:
             """simple docstring"""




             pass






      @abstractmethod
      def __eq__( self						:					T      ,       lowercase_						:					object			) ->						bool:
             """simple docstring"""




             pass




lowerCamelCase						 =	TypeVar('T', bound=Comparable)




class A  (       Generic[T]					):






      def __init__( self						:					Optional[Any]			) ->						None:
             """simple docstring"""




             _lowerCamelCase	:		list[T]          =[]
             _lowerCamelCase	:		int          =0






      def __repr__( self						:					int			) ->						str:
             """simple docstring"""




             return str(self.h			)






      def 	lowerCamelCase	( self						:					str      ,       lowercase_						:					int			) ->						int | None:
             """simple docstring"""




             if child_idx > 0:
                    return (child_idx - 1) // 2
             return None






      def 	lowerCamelCase	( self						:					Union[str, Any]      ,       lowercase_						:					int			) ->						int | None:
             """simple docstring"""




             _lowerCamelCase	:		Dict          =2 * parent_idx + 1
             if left_child_index < self.heap_size:
                    return left_child_index
             return None






      def 	lowerCamelCase	( self						:					List[str]      ,       lowercase_						:					int			) ->						int | None:
             """simple docstring"""




             _lowerCamelCase	:		Optional[int]          =2 * parent_idx + 2
             if right_child_index < self.heap_size:
                    return right_child_index
             return None






      def 	lowerCamelCase	( self						:					Any      ,       lowercase_						:					int			) ->						None:
             """simple docstring"""




             if index < self.heap_size:
                    _lowerCamelCase	:		int          =index
                    _lowerCamelCase	:		Any          =self.left_child_idx(lowercase_			)
                    _lowerCamelCase	:		int          =self.right_child_idx(lowercase_			)
                    # check which child is larger than its parent
                    if left_child is not None and self.h[left_child] > self.h[violation]:
                           _lowerCamelCase	:		str          =left_child
                    if right_child is not None and self.h[right_child] > self.h[violation]:
                           _lowerCamelCase	:		str          =right_child
                    # if violation indeed exists
                    if violation != index:
                           # swap to fix the violation
                           _lowerCamelCase     ,					_lowerCamelCase	:		List[str]          =self.h[index], self.h[violation]
                           # fix the subsequent violation recursively if any
                           self.max_heapify(lowercase_			)






      def 	lowerCamelCase	( self						:					int      ,       lowercase_						:					Iterable[T]			) ->						None:
             """simple docstring"""




             _lowerCamelCase	:		List[Any]          =list(lowercase_			)
             _lowerCamelCase	:		Dict          =len(self.h			)
             if self.heap_size > 1:
                    # max_heapify from right to left but exclude leaves (last level)
                    for i in range(self.heap_size // 2 - 1      ,       -1      ,       -1			):
                           self.max_heapify(lowercase_			)






      def 	lowerCamelCase	( self						:					Dict			) ->						T:
             """simple docstring"""




             if self.heap_size >= 2:
                    _lowerCamelCase	:		Optional[int]          =self.h[0]
                    _lowerCamelCase	:		Optional[int]          =self.h.pop(-1			)
                    self.heap_size -= 1
                    self.max_heapify(0			)
                    return me
             elif self.heap_size == 1:
                    self.heap_size -= 1
                    return self.h.pop(-1			)
             else:
                    raise Exception('Empty heap'			)






      def 	lowerCamelCase	( self						:					Tuple      ,       lowercase_						:					T			) ->						None:
             """simple docstring"""




             self.h.append(lowercase_			)
             _lowerCamelCase	:		List[Any]          =(self.heap_size - 1) // 2
             self.heap_size += 1
             while idx >= 0:
                    self.max_heapify(lowercase_			)
                    _lowerCamelCase	:		Tuple          =(idx - 1) // 2






      def 	lowerCamelCase	( self						:					Optional[Any]			) ->						None:
             """simple docstring"""




             _lowerCamelCase	:		Union[str, Any]          =self.heap_size
             for j in range(size - 1      ,       0      ,       -1			):
                    _lowerCamelCase     ,					_lowerCamelCase	:		Optional[Any]          =self.h[j], self.h[0]
                    self.heap_size -= 1
                    self.max_heapify(0			)
             _lowerCamelCase	:		Union[str, Any]          =size


if __name__ == "__main__":
 import doctest

 # run doc test
 doctest.testmod()

 # demo
 for unsorted in [
     [0],
     [2],
     [3, 5],
     [5, 3],
     [5, 5],
     [0, 0, 0, 0],
     [1, 1, 1, 1],
     [2, 2, 3, 5],
     [0, 2, 2, 3, 5],
     [2, 5, 3, 0, 2, 3, 0, 3],
     [6, 1, 2, 7, 9, 3, 4, 5, 10, 8],
     [1_03, 9, 1, 7, 11, 15, 25, 2_01, 2_09, 1_07, 5],
     [-45, -2, -5],
 ]:
  print(F"""unsorted array: {unsorted}""")

  lowerCamelCase						 =	Heap()
  heap.build_max_heap(unsorted)
  print(F"""after build heap: {heap}""")

  print(F"""max value: {heap.extract_max()}""")
  print(F"""after max value removed: {heap}""")

  heap.insert(1_00)
  print(F"""after new value 100 inserted: {heap}""")

  heap.heap_sort()
  print(F"""heap-sorted array: {heap}\n""")


