




from __future__ import annotations

from collections.abc import Iterable


class     __SCREAMING_SNAKE_CASE							:

					def __init__(    self			,	__lowercase			,	__lowercase ):







						'''simple docstring'''




						lowerCamelCase_       ,      lowerCamelCase_							:		Optional[int]							       =							float(__lowercase ), float(__lowercase )

					def __eq__(    self			,	__lowercase ):







						'''simple docstring'''




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

					def __ne__(    self			,	__lowercase ):







						'''simple docstring'''




						return not self == other

					def __gt__(    self			,	__lowercase ):







						'''simple docstring'''




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

					def __lt__(    self			,	__lowercase ):







						'''simple docstring'''




						return not self > other

					def __ge__(    self			,	__lowercase ):







						'''simple docstring'''




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

					def __le__(    self			,	__lowercase ):







						'''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  snake_case (							A						,       )							->							list[Point]:




	'''simple docstring'''


	lowerCamelCase_							:		list[Point]							       =							[]
	if list_of_tuples:
		for p in list_of_tuples:
			if isinstance(A						,       A      ):
				points.append(A      )
			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  snake_case (							A      )							->							list[Point]:




	'''simple docstring'''


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

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

	return _construct_points(A      )






def  snake_case (							A						,       A						,       A      )							->							float:




	'''simple docstring'''


	lowerCamelCase_							:		str							       =							(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  snake_case (							A      )							->							list[Point]:




	'''simple docstring'''


	lowerCamelCase_							:		Dict							       =							sorted(_validate_input(A      )      )
	lowerCamelCase_							:		List[Any]							       =							len(A      )
	lowerCamelCase_							:		Optional[int]							       =							set()

	for i in range(n - 1      ):
		for j in range(i + 1						,       A      ):
			lowerCamelCase_							:		Tuple							       =							False
			lowerCamelCase_							:		Any							       =							True
			for k in range(A      ):
				if k != i and k != j:
					lowerCamelCase_							:		str							       =							_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_							:		List[Any]							       =							False
							break

				if points_left_of_ij and points_right_of_ij:
					lowerCamelCase_							:		List[Any]							       =							False
					break

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

	return sorted(A      )






def  snake_case (							A      )							->							list[Point]:




	'''simple docstring'''


	lowerCamelCase_							:		List[str]							       =							sorted(_validate_input(A      )      )
	lowerCamelCase_							:		Optional[Any]							       =							len(A      )

	# 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_							:		Optional[int]							       =							points[0]
	lowerCamelCase_							:		Optional[Any]							       =							points[n - 1]

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

	for i in range(1						,       n - 1      ):
		lowerCamelCase_							:		List[str]							       =							_det(A						,       A						,       points[i]      )

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

	_construct_hull(A						,       A						,       A						,       A      )
	_construct_hull(A						,       A						,       A						,       A      )

	return sorted(A      )






def  snake_case (							A						,       A						,       A						,       A      )							->							None:




	'''simple docstring'''


	if points:
		lowerCamelCase_							:		Any							       =							None
		lowerCamelCase_							:		List[Any]							       =							float('-inf'      )
		lowerCamelCase_							:		Any							       =							[]

		for p in points:
			lowerCamelCase_							:		int							       =							_det(A						,       A						,       A      )

			if det > 0:
				candidate_points.append(A      )

				if det > extreme_point_distance:
					lowerCamelCase_							:		str							       =							det
					lowerCamelCase_							:		Union[str, Any]							       =							p

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






def  snake_case (							A      )							->							list[Point]:




	'''simple docstring'''


	lowerCamelCase_							:		int							       =							sorted(_validate_input(A      )      )
	lowerCamelCase_							:		List[str]							       =							len(A      )

	lowerCamelCase_							:		List[Any]							       =							points[:2]
	for i in range(2						,       A      ):
		lowerCamelCase_							:		int							       =							_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(A						,       A      ):
		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(A      ) > 3 else convex_hull      )






def  snake_case (							)							->							Optional[int]:




	'''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_							:		Union[str, Any]							       =							convex_hull_bf(A      )

	lowerCamelCase_							:		Any							       =							convex_hull_recursive(A      )
	assert results_bf == results_recursive

	lowerCamelCase_							:		Any							       =							convex_hull_melkman(A      )
	assert results_bf == results_melkman

	print(A      )


if __name__ == "__main__":
							main()






from __future__ import annotations






def  snake_case (							A						,       A      )							->							Union[str, Any]:




	'''simple docstring'''


	lowerCamelCase_							:		Tuple							       =							0
	lowerCamelCase_							:		str							       =							len(A      ) - 1
	while left <= right:
		lowerCamelCase_							:		str							       =							(left + right) // 2
		if left == right:
			if sorted_list[middle] < item:
				lowerCamelCase_							:		List[Any]							       =							middle + 1
			break
		elif sorted_list[middle] < item:
			lowerCamelCase_							:		Any							       =							middle + 1
		else:
			lowerCamelCase_							:		Optional[int]							       =							middle - 1
	sorted_list.insert(A						,       A      )
	return sorted_list






def  snake_case (							A						,       A      )							->							Union[str, Any]:




	'''simple docstring'''


	lowerCamelCase_							:		List[Any]							       =							[]
	while left and right:
		if left[0][0] < right[0][0]:
			result.append(left.pop(0      )      )
		else:
			result.append(right.pop(0      )      )
	return result + left + right






def  snake_case (							A      )							->							Any:




	'''simple docstring'''


	lowerCamelCase_							:		List[Any]							       =							len(A      )
	if length <= 1:
		return list_ad
	lowerCamelCase_							:		Any							       =							length // 2
	return merge(sortlist_ad(list_ad[:middle]      )						,       sortlist_ad(list_ad[middle:]      )      )






def  snake_case (							A      )							->							list[int]:




	'''simple docstring'''


	if len(A      ) <= 1:
		return collection
	lowerCamelCase_							:		Tuple							       =							[]
	lowerCamelCase_							:		int							       =							False
	for i in range(0						,       len(A      )						,       2      ):
		if i == len(A      ) - 1:
			lowerCamelCase_							:		Any							       =							True
		else:
			if collection[i] < collection[i + 1]:
				two_paired_list.append([collection[i], collection[i + 1]]      )
			else:
				two_paired_list.append([collection[i + 1], collection[i]]      )
	lowerCamelCase_							:		Union[str, Any]							       =							sortlist_ad(A      )
	lowerCamelCase_							:		int							       =							[i[0] for i in sorted_list_ad]
	result.append(sorted_list_ad[-1][1]      )
	if has_last_odd_item:
		lowerCamelCase_							:		List[str]							       =							collection[-1]
		lowerCamelCase_							:		Optional[Any]							       =							binary_search_insertion(A						,       A      )
	lowerCamelCase_							:		Optional[Any]							       =							False
	for i in range(len(A      ) - 1      ):
		if result[i] == collection[-1] and has_last_odd_item:
			lowerCamelCase_							:		Optional[Any]							       =							True
		lowerCamelCase_							:		Dict							       =							sorted_list_ad[i][1]
		# If last_odd_item is inserted before the item's index,
		# you should forward index one more.
		if is_last_odd_item_inserted_before_this_index:
			lowerCamelCase_							:		Dict							       =							result[: i + 2] + binary_search_insertion(result[i + 2 :]						,       A      )
		else:
			lowerCamelCase_							:		str							       =							result[: i + 1] + binary_search_insertion(result[i + 1 :]						,       A      )

	return result


if __name__ == "__main__":
							UpperCamelCase__		=						input('Enter numbers separated by a comma:\n').strip()
							UpperCamelCase__		=						[int(item) for item in user_input.split(',')]
							print(merge_insertion_sort(unsorted))
