


from __future__ import annotations

from collections.abc import Iterable







class 					snake_case__:







						'''simple docstring'''




						def __init__(					self ,    __lowercase ,    __lowercase				)       ->     List[str]:
										lowerCAmelCase_					,	lowerCAmelCase_			:   Tuple     					=					float(__lowercase				), float(__lowercase				)




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




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




						def __gt__(					self ,    __lowercase				)       ->     Optional[Any]:
										if self.x > other.x:
														return True
										elif self.x == other.x:
														return self.y > other.y
										return False




						def __lt__(					self ,    __lowercase				)       ->     int:
										return not self > other




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




						def __le__(					self ,    __lowercase				)       ->     Union[str, Any]:
										if self.x < other.x:
														return True
										elif self.x == other.x:
														return self.y <= other.y
										return False




						def __repr__(					self				)       ->     Tuple:
										return f"""({self.x}, {self.y})"""




						def __hash__(					self				)       ->     List[str]:
										return hash(self.x				)






def       lowerCAmelCase			(		lowerCAmelCase_			, )->			list[Point]:
				lowerCAmelCase_			:   list[Point]     					=					[]
				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]:

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

				if not points:
								lowerCAmelCase_			:   Tuple     					=					f"""Expecting a list of points but got {points}"""
								raise ValueError(lowerCAmelCase_			)

				return _construct_points(lowerCAmelCase_			)



def       lowerCAmelCase			(		lowerCAmelCase_			, lowerCAmelCase_			, lowerCAmelCase_			)->			float:
				lowerCAmelCase_			:   List[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       lowerCAmelCase			(		lowerCAmelCase_			)->			list[Point]:
				lowerCAmelCase_			:   Union[str, Any]     					=					sorted(_validate_input(lowerCAmelCase_			)			)
				lowerCAmelCase_			:   Any     					=					len(lowerCAmelCase_			)
				lowerCAmelCase_			:   List[Any]     					=					set()

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

																				if det_k > 0:
																								lowerCAmelCase_			:   Dict     					=					True
																				elif det_k < 0:
																								lowerCAmelCase_			:   Dict     					=					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_			:   Dict     					=					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(lowerCAmelCase_			)



def       lowerCAmelCase			(		lowerCAmelCase_			)->			list[Point]:
				lowerCAmelCase_			:   Optional[int]     					=					sorted(_validate_input(lowerCAmelCase_			)			)
				lowerCAmelCase_			:   Optional[Any]     					=					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_			:   List[str]     					=					points[0]
				lowerCAmelCase_			:   Optional[Any]     					=					points[n - 1]

				lowerCAmelCase_			:   List[Any]     					=					{left_most_point, right_most_point}
				lowerCAmelCase_			:   Any     					=					[]
				lowerCAmelCase_			:   Optional[int]     					=					[]

				for i in range(1			, n - 1			):
								lowerCAmelCase_			:   List[str]     					=					_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_			, lowerCAmelCase_			, lowerCAmelCase_			, lowerCAmelCase_			)->			None:
				if points:
								lowerCAmelCase_			:   str     					=					None
								lowerCAmelCase_			:   Optional[Any]     					=					float('''-inf'''			)
								lowerCAmelCase_			:   Optional[Any]     					=					[]

								for p in points:
												lowerCAmelCase_			:   List[str]     					=					_det(lowerCAmelCase_			, lowerCAmelCase_			, lowerCAmelCase_			)

												if det > 0:
																candidate_points.append(lowerCAmelCase_			)

																if det > extreme_point_distance:
																				lowerCAmelCase_			:   List[Any]     					=					det
																				lowerCAmelCase_			:   int     					=					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]:
				lowerCAmelCase_			:   List[str]     					=					sorted(_validate_input(lowerCAmelCase_			)			)
				lowerCAmelCase_			:   Optional[int]     					=					len(lowerCAmelCase_			)

				lowerCAmelCase_			:   Union[str, Any]     					=					points[:2]
				for i in range(2			, lowerCAmelCase_			):
								lowerCAmelCase_			:   Optional[Any]     					=					_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_			:   Optional[int]     					=					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			(		)->			int:
				lowerCAmelCase_			:   List[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_			:   List[Any]     					=					convex_hull_bf(lowerCAmelCase_			)

				lowerCAmelCase_			:   Any     					=					convex_hull_recursive(lowerCAmelCase_			)
				assert results_bf == results_recursive

				lowerCAmelCase_			:   Optional[Any]     					=					convex_hull_melkman(lowerCAmelCase_			)
				assert results_bf == results_melkman

				print(lowerCAmelCase_			)


if __name__ == "__main__":
						main()



def       lowerCAmelCase			(		lowerCAmelCase_			)->			int:
				lowerCAmelCase_			:   Optional[int]     					=					len(lowerCAmelCase_			)
				if n in (0, 1):
								return 0
				return sum(query * (n - i - 1) for i, query in enumerate(sorted(lowerCAmelCase_			)			)			)


if __name__ == "__main__":
						import doctest

						doctest.testmod()