


"""simple docstring"""
from __future__ import annotations

from collections.abc import Iterable



class      _UpperCAmelCase					:






		'''simple docstring'''

		def __init__(self							,			a_							,			a_   ):





			'''simple docstring'''

			__snake_case      ,				__snake_case      :		str         =							float(a_   ), float(a_   )



		def __eq__(self							,			a_   ):





			'''simple docstring'''

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



		def __ne__(self							,			a_   ):





			'''simple docstring'''

			return not self == other



		def __gt__(self							,			a_   ):





			'''simple docstring'''

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



		def __lt__(self							,			a_   ):





			'''simple docstring'''

			return not self > other



		def __ge__(self							,			a_   ):





			'''simple docstring'''

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



		def __le__(self							,			a_   ):





			'''simple docstring'''

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



		def __repr__(self   ):





			'''simple docstring'''

			return f"""({self.x}, {self.y})"""



		def __hash__(self   ):





			'''simple docstring'''

			return hash(self.x   )






def 						lowercase				(	_snake_case		: list[Point] | list[list[float]] | Iterable[list[float]]	,  )	->list[Point]:
	"""simple docstring"""





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





	if not hasattr(_snake_case	,  '''__iter__'''	):
		__snake_case      :		Optional[Any]         =							f"""Expecting an iterable object but got an non-iterable type {points}"""
		raise ValueError(_snake_case	)

	if not points:
		__snake_case      :		str         =							f"""Expecting a list of points but got {points}"""
		raise ValueError(_snake_case	)

	return _construct_points(_snake_case	)






def 						lowercase				(	_snake_case		: Point	,  _snake_case		: Point	,  _snake_case		: Point	)	->float:
	"""simple docstring"""





	__snake_case      :		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 						lowercase				(	_snake_case		: list[Point]	)	->list[Point]:
	"""simple docstring"""





	__snake_case      :		List[Any]         =							sorted(_validate_input(_snake_case	)	)
	__snake_case      :		Optional[int]         =							len(_snake_case	)
	__snake_case      :		List[str]         =							set()

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

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

				if points_left_of_ij and points_right_of_ij:
					__snake_case      :		List[str]         =							False
					break

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

	return sorted(_snake_case	)






def 						lowercase				(	_snake_case		: list[Point]	)	->list[Point]:
	"""simple docstring"""





	__snake_case      :		str         =							sorted(_validate_input(_snake_case	)	)
	__snake_case      :		List[Any]         =							len(_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

	__snake_case      :		List[str]         =							points[0]
	__snake_case      :		str         =							points[n - 1]

	__snake_case      :		Union[str, Any]         =							{left_most_point, right_most_point}
	__snake_case      :		str         =							[]
	__snake_case      :		List[Any]         =							[]

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

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

	_construct_hull(_snake_case	,  _snake_case	,  _snake_case	,  _snake_case	)
	_construct_hull(_snake_case	,  _snake_case	,  _snake_case	,  _snake_case	)

	return sorted(_snake_case	)






def 						lowercase				(	_snake_case		: list[Point]	,  _snake_case		: Point	,  _snake_case		: Point	,  _snake_case		: set[Point]	)	->None:
	"""simple docstring"""





	if points:
		__snake_case      :		int         =							None
		__snake_case      :		Dict         =							float('''-inf'''	)
		__snake_case      :		Union[str, Any]         =							[]

		for p in points:
			__snake_case      :		Union[str, Any]         =							_det(_snake_case	,  _snake_case	,  _snake_case	)

			if det > 0:
				candidate_points.append(_snake_case	)

				if det > extreme_point_distance:
					__snake_case      :		int         =							det
					__snake_case      :		Optional[Any]         =							p

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






def 						lowercase				(	_snake_case		: list[Point]	)	->list[Point]:
	"""simple docstring"""





	__snake_case      :		List[str]         =							sorted(_validate_input(_snake_case	)	)
	__snake_case      :		int         =							len(_snake_case	)

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

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






def 						lowercase				(	)	->List[Any]:
	"""simple docstring"""





	__snake_case      :		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)]
	__snake_case      :		Tuple         =							convex_hull_bf(_snake_case	)

	__snake_case      :		List[Any]         =							convex_hull_recursive(_snake_case	)
	assert results_bf == results_recursive

	__snake_case      :		Tuple         =							convex_hull_melkman(_snake_case	)
	assert results_bf == results_melkman

	print(_snake_case	)


if __name__ == "__main__":
			main()







def 		lowerCAmelCase_     (     _SCREAMING_SNAKE_CASE      ,	_SCREAMING_SNAKE_CASE      ,	_SCREAMING_SNAKE_CASE  )   ->      Dict:

							"""simple docstring"""






							if power < 0:
														return -1
							base %= mod
							_UpperCAmelCase  :			Optional[Any]	       =		1

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

							return result




def 		lowerCAmelCase_     (     )   ->      List[str]:

							"""simple docstring"""






							print(modular_exponential(3      ,	2_0_0      ,	1_3  )  )


if __name__ == "__main__":
				import doctest

				doctest.testmod()

				main()




