





'''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()








'''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()

