



'''simple docstring'''



from __future__ import annotations

from collections.abc import Iterable






class        UpperCAmelCase__						:



					def __init__(     self      ,					UpperCamelCase      ,					UpperCamelCase  )  ->      Tuple:
						__lowerCAmelCase				,							__lowerCAmelCase       				=	float(UpperCamelCase  ), float(UpperCamelCase  )



					def __eq__(     self      ,					UpperCamelCase  )  ->      List[str]:
						return self.x == other.x and self.y == other.y



					def __ne__(     self      ,					UpperCamelCase  )  ->      Optional[Any]:
						return not self == other



					def __gt__(     self      ,					UpperCamelCase  )  ->      List[str]:
						if self.x > other.x:
							return True
						elif self.x == other.x:
							return self.y > other.y
						return False



					def __lt__(     self      ,					UpperCamelCase  )  ->      Dict:
						return not self > other



					def __ge__(     self      ,					UpperCamelCase  )  ->      List[str]:
						if self.x > other.x:
							return True
						elif self.x == other.x:
							return self.y >= other.y
						return False



					def __le__(     self      ,					UpperCamelCase  )  ->      str:
						if self.x < other.x:
							return True
						elif self.x == other.x:
							return self.y <= other.y
						return False



					def __repr__(     self  )  ->      int:
						return F'''({self.x}, {self.y})'''



					def __hash__(     self  )  ->      Union[str, Any]:
						return hash(self.x  )



def 	__lowerCAmelCase       (				lowerCamelCase :    list[Point] | list[list[float]] | Iterable[list[float]]					,		):






	'''simple docstring'''




	__lowerCAmelCase       				=	[]
	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 	__lowerCAmelCase       (				lowerCamelCase :    list[Point] | list[list[float]]       ):






	'''simple docstring'''




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

	if not points:
		__lowerCAmelCase       				=	f'''Expecting a list of points but got {points}'''
		raise ValueError(lowerCamelCase       )

	return _construct_points(lowerCamelCase       )



def 	__lowerCAmelCase       (				lowerCamelCase :    Point					,		lowerCamelCase :    Point					,		lowerCamelCase :    Point       ):






	'''simple docstring'''




	__lowerCAmelCase       				=	(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 	__lowerCAmelCase       (				lowerCamelCase :    list[Point]       ):






	'''simple docstring'''




	__lowerCAmelCase       				=	sorted(_validate_input(lowerCamelCase       )       )
	__lowerCAmelCase       				=	len(lowerCamelCase       )
	__lowerCAmelCase       				=	set()

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

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

				if points_left_of_ij and points_right_of_ij:
					__lowerCAmelCase       				=	False
					break

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

	return sorted(lowerCamelCase       )



def 	__lowerCAmelCase       (				lowerCamelCase :    list[Point]       ):






	'''simple docstring'''




	__lowerCAmelCase       				=	sorted(_validate_input(lowerCamelCase       )       )
	__lowerCAmelCase       				=	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

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

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

	for i in range(1					,		n - 1       ):
		__lowerCAmelCase       				=	_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 	__lowerCAmelCase       (				lowerCamelCase :    list[Point]					,		lowerCamelCase :    Point					,		lowerCamelCase :    Point					,		lowerCamelCase :    set[Point]       ):






	'''simple docstring'''




	if points:
		__lowerCAmelCase       				=	None
		__lowerCAmelCase       				=	float("-inf"       )
		__lowerCAmelCase       				=	[]

		for p in points:
			__lowerCAmelCase       				=	_det(lowerCamelCase					,		lowerCamelCase					,		lowerCamelCase       )

			if det > 0:
				candidate_points.append(lowerCamelCase       )

				if det > extreme_point_distance:
					__lowerCAmelCase       				=	det
					__lowerCAmelCase       				=	p

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



def 	__lowerCAmelCase       (				lowerCamelCase :    list[Point]       ):






	'''simple docstring'''




	__lowerCAmelCase       				=	sorted(_validate_input(lowerCamelCase       )       )
	__lowerCAmelCase       				=	len(lowerCamelCase       )

	__lowerCAmelCase       				=	points[:2]
	for i in range(2					,		lowerCamelCase       ):
		__lowerCAmelCase       				=	_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       				=	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 	__lowerCAmelCase       (				):






	'''simple docstring'''




	__lowerCAmelCase       				=	[
	    (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       				=	convex_hull_bf(lowerCamelCase       )

	__lowerCAmelCase       				=	convex_hull_recursive(lowerCamelCase       )
	assert results_bf == results_recursive

	__lowerCAmelCase       				=	convex_hull_melkman(lowerCamelCase       )
	assert results_bf == results_melkman

	print(lowerCamelCase       )


if __name__ == "__main__":
	main()




'''simple docstring'''



import math



def 	__lowerCAmelCase       (				lowerCamelCase :    int       ):






	'''simple docstring'''




	if not isinstance(lowerCamelCase					,		lowerCamelCase       ):
		__lowerCAmelCase       				=	f'''Input value of [number={number}] must be an integer'''
		raise TypeError(lowerCamelCase       )
	if number < 1:
		__lowerCAmelCase       				=	f'''Input value of [number={number}] must be a positive integer'''
		raise ValueError(lowerCamelCase       )
	__lowerCAmelCase       				=	[number]
	while number != 1:
		if number % 2 == 0:
			__lowerCAmelCase       				=	math.floor(math.sqrt(lowerCamelCase       )       )
		else:
			__lowerCAmelCase       				=	math.floor(
			    math.sqrt(lowerCamelCase       ) * math.sqrt(lowerCamelCase       ) * math.sqrt(lowerCamelCase       )       )
		sequence.append(lowerCamelCase       )
	return sequence


if __name__ == "__main__":
	import doctest

	doctest.testmod()