code: 
  
  
  
  
  
  '''simple docstring'''
  
  
  from __future__ import annotations
  
  from collections.abc import Iterable
  
  
  
  class 							__UpperCAmelCase  :
  
  
  
  
  
  
  
  		'''simple docstring'''
  
  
  
  
  
  
  
  		def __init__(self						:      List[str]      ,      _lowerCAmelCase						:      List[Any]      ,      _lowerCAmelCase						:      Any      ):
  			A							  =      float(_lowerCAmelCase      ), float(_lowerCAmelCase      )
  
  
  
  
  
  
  
  		def __eq__(self						:      Any      ,      _lowerCAmelCase						:      List[Any]      ):
  			return self.x == other.x and self.y == other.y
  
  
  
  
  
  
  
  		def __ne__(self						:      Optional[int]      ,      _lowerCAmelCase						:      int      ):
  			return not self == other
  
  
  
  
  
  
  
  		def __gt__(self						:      List[Any]      ,      _lowerCAmelCase						:      Dict      ):
  
  
  
  
  
  
  			if self.x > other.x:
  				return True
  			elif self.x == other.x:
  				return self.y > other.y
  			return False
  
  
  
  
  
  
  
  		def __lt__(self						:      List[Any]      ,      _lowerCAmelCase						:      str      ):
  			return not self > other
  
  
  
  
  
  
  
  		def __ge__(self						:      Optional[Any]      ,      _lowerCAmelCase						:      Optional[Any]      ):
  
  
  
  
  
  
  			if self.x > other.x:
  				return True
  			elif self.x == other.x:
  				return self.y >= other.y
  			return False
  
  
  
  
  
  
  
  		def __le__(self						:      Union[str, Any]      ,      _lowerCAmelCase						:      Optional[int]      ):
  
  
  
  
  
  
  			if self.x < other.x:
  				return True
  			elif self.x == other.x:
  				return self.y <= other.y
  			return False
  
  
  
  
  
  
  
  		def __repr__(self						:      List[Any]      ):
  			return F"""({self.x}, {self.y})"""
  
  
  
  
  
  
  
  		def __hash__(self						:      Dict      ):
  			return hash(self.x      )
  
  
  
  
  
  
  def        __a (     UpperCAmelCase       ,			)      ->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 (     UpperCAmelCase    )      ->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 (     UpperCAmelCase       ,			UpperCAmelCase       ,			UpperCAmelCase    )      ->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 (     UpperCAmelCase    )      ->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							  =      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 (     UpperCAmelCase    )      ->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 (     UpperCAmelCase       ,			UpperCAmelCase       ,			UpperCAmelCase       ,			UpperCAmelCase    )      ->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 (     UpperCAmelCase    )      ->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 (     )      ->Dict:
  
  
  
  	"""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()
  
  
style_context: 
  
  
  
  
  
  '''simple docstring'''
  
  
  class 							__UpperCAmelCase  :
  
  
  
  
  
  
  
  		'''simple docstring'''
  
  
  
  
  
  
  
  		def __init__(self						:      List[str]      ):
  			# numbermap keys are the number and its values are lists of indexes sorted
  			# in ascending order
  			A							  =      {}
  			# indexmap keys are an index and it's values are the number at that index
  			A							  =      {}
  
  
  
  
  
  
  
  		def        A     (self						:      Union[str, Any]      ,      _lowerCAmelCase						:      list | str | range      ,      _lowerCAmelCase						:      int      ):
  			if isinstance(_lowerCAmelCase      ,      (range, str)      ):
  				A							  =      list(_lowerCAmelCase      )
  			elif not isinstance(_lowerCAmelCase      ,      _lowerCAmelCase      ):
  				raise TypeError(
  				    """binary_search_delete() only accepts either a list, range or str"""      )
  
  			A							  =      0
  			A							  =      len(_lowerCAmelCase      ) - 1
  
  			while low <= high:
  				A							  =      (low + high) // 2
  				if array[mid] == item:
  					array.pop(_lowerCAmelCase      )
  					return array
  				elif array[mid] < item:
  					A							  =      mid + 1
  				else:
  					A							  =      mid - 1
  			raise ValueError(
  			    """Either the item is not in the array or the array was unsorted"""      )
  
  
  
  
  
  
  
  		def        A     (self						:      Dict      ,      _lowerCAmelCase						:      list | str | range      ,      _lowerCAmelCase						:      int      ):
  			if isinstance(_lowerCAmelCase      ,      (range, str)      ):
  				A							  =      list(_lowerCAmelCase      )
  			elif not isinstance(_lowerCAmelCase      ,      _lowerCAmelCase      ):
  				raise TypeError(
  				    """binary_search_insert() only accepts either a list, range or str"""      )
  
  			A							  =      0
  			A							  =      len(_lowerCAmelCase      ) - 1
  
  			while low <= high:
  				A							  =      (low + high) // 2
  				if array[mid] == index:
  					# If the item already exists in the array,
  					# insert it after the existing item
  					array.insert(mid + 1      ,      _lowerCAmelCase      )
  					return array
  				elif array[mid] < index:
  					A							  =      mid + 1
  				else:
  					A							  =      mid - 1
  
          # If the item doesn't exist in the array, insert it at the appropriate position
  			array.insert(_lowerCAmelCase      ,      _lowerCAmelCase      )
  			return array
  
  
  
  
  
  
  
  		def        A     (self						:      List[str]      ,      _lowerCAmelCase						:      int      ,      _lowerCAmelCase						:      int      ):
  			# Remove previous index
  			if index in self.indexmap:
  				A							  =      self.indexmap[index]
  				if len(self.numbermap[n]      ) == 1:
  					del self.numbermap[n]
  				else:
  					A							  =      self.binary_search_delete(self.numbermap[n]      ,      _lowerCAmelCase      )
  
          # Set new index
  			A							  =      number
  
  			# Number not seen before or empty so insert number value
  			if number not in self.numbermap:
  				A							  =      [index]
  
  			# Here we need to perform a binary search insertion in order to insert
  			# The item in the correct place
  			else:
  				A							  =      self.binary_search_insert(
  				    self.numbermap[number]      ,      _lowerCAmelCase      )
  
  
  
  
  
  
  
  		def        A     (self						:      int      ,      _lowerCAmelCase						:      int      ):
  			return self.numbermap.get(_lowerCAmelCase      ,      [-1]      )[0]
  
  
  if __name__ == "__main__":
  				import doctest
  
  				doctest.testmod()
  
  