
from __future__ import annotations

from collections.abc import Iterable





class 						lowercase       :
					def __init__(		self ,	SCREAMING_SNAKE_CASE__ ,	SCREAMING_SNAKE_CASE__    ):
								"""simple docstring"""







								lowerCAmelCase__      ,				lowerCAmelCase__ :    List[str]				      =			float(SCREAMING_SNAKE_CASE__    ), float(SCREAMING_SNAKE_CASE__    )
					def __eq__(		self ,	SCREAMING_SNAKE_CASE__    ):
								"""simple docstring"""







								return self.x == other.x and self.y == other.y
					def __ne__(		self ,	SCREAMING_SNAKE_CASE__    ):
								"""simple docstring"""







								return not self == other
					def __gt__(		self ,	SCREAMING_SNAKE_CASE__    ):
								"""simple docstring"""







								if self.x > other.x:
											return True
								elif self.x == other.x:
											return self.y > other.y
								return False
					def __lt__(		self ,	SCREAMING_SNAKE_CASE__    ):
								"""simple docstring"""







								return not self > other
					def __ge__(		self ,	SCREAMING_SNAKE_CASE__    ):
								"""simple docstring"""







								if self.x > other.x:
											return True
								elif self.x == other.x:
											return self.y >= other.y
								return False
					def __le__(		self ,	SCREAMING_SNAKE_CASE__    ):
								"""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      _a     (   __UpperCamelCase       :  list[Point] | list[list[float]] | Iterable[list[float]]	,):
			lowerCAmelCase__ :    list[Point]				      =			[]
			if list_of_tuples:
						for p in list_of_tuples:
									if isinstance(__UpperCamelCase	,__UpperCamelCase    ):
												points.append(__UpperCamelCase    )
									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] | list[list[float]]    ):

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

			if not points:
						lowerCAmelCase__ :    Union[str, Any]				      =			f'''Expecting a list of points but got {points}'''
						raise ValueError(__UpperCamelCase    )

			return _construct_points(__UpperCamelCase    )



def      _a     (   __UpperCamelCase       :  Point	,__UpperCamelCase       :  Point	,__UpperCamelCase       :  Point    ):
			lowerCAmelCase__ :    int				      =			(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]    ):
			lowerCAmelCase__ :    List[Any]				      =			sorted(_validate_input(__UpperCamelCase    )    )
			lowerCAmelCase__ :    int				      =			len(__UpperCamelCase    )
			lowerCAmelCase__ :    Tuple				      =			set()

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

															if det_k > 0:
																		lowerCAmelCase__ :    int				      =			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__ :    Union[str, Any]				      =			False
															break

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

			return sorted(__UpperCamelCase    )



def      _a     (   __UpperCamelCase       :  list[Point]    ):
			lowerCAmelCase__ :    Dict				      =			sorted(_validate_input(__UpperCamelCase    )    )
			lowerCAmelCase__ :    List[Any]				      =			len(__UpperCamelCase    )

			# 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__ :    int				      =			points[n - 1]

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

			for i in range(1	,n - 1    ):
						lowerCAmelCase__ :    Any				      =			_det(__UpperCamelCase	,__UpperCamelCase	,points[i]    )

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

			_construct_hull(__UpperCamelCase	,__UpperCamelCase	,__UpperCamelCase	,__UpperCamelCase    )
			_construct_hull(__UpperCamelCase	,__UpperCamelCase	,__UpperCamelCase	,__UpperCamelCase    )

			return sorted(__UpperCamelCase    )



def      _a     (   __UpperCamelCase       :  list[Point]	,__UpperCamelCase       :  Point	,__UpperCamelCase       :  Point	,__UpperCamelCase       :  set[Point]    ):
			if points:
						lowerCAmelCase__ :    Optional[Any]				      =			None
						lowerCAmelCase__ :    Union[str, Any]				      =			float('''-inf'''    )
						lowerCAmelCase__ :    List[Any]				      =			[]

						for p in points:
									lowerCAmelCase__ :    Union[str, Any]				      =			_det(__UpperCamelCase	,__UpperCamelCase	,__UpperCamelCase    )

									if det > 0:
												candidate_points.append(__UpperCamelCase    )

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

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



def      _a     (   __UpperCamelCase       :  list[Point]    ):
			lowerCAmelCase__ :    str				      =			sorted(_validate_input(__UpperCamelCase    )    )
			lowerCAmelCase__ :    Union[str, Any]				      =			len(__UpperCamelCase    )

			lowerCAmelCase__ :    Dict				      =			points[:2]
			for i in range(2	,__UpperCamelCase    ):
						lowerCAmelCase__ :    Tuple				      =			_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__ :    int				      =			points[i]
			i += 1

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



def      _a     (   ):
			lowerCAmelCase__ :    Optional[int]				      =			[
			    (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__ :    str				      =			convex_hull_bf(__UpperCamelCase    )

			lowerCAmelCase__ :    List[Any]				      =			convex_hull_recursive(__UpperCamelCase    )
			assert results_bf == results_recursive

			lowerCAmelCase__ :    Dict				      =			convex_hull_melkman(__UpperCamelCase    )
			assert results_bf == results_melkman

			print(__UpperCamelCase    )


if __name__ == "__main__":
							main()





# tests directory-specific settings - this file is run automatically
# by pytest before any tests are run

import sys
import warnings
from os.path import abspath, dirname, join


# allow having multiple repository checkouts and not needing to remember to rerun
# 'pip install -e .[dev]' when switching between checkouts and running tests.
A__       :   Optional[Any]   						=					abspath(join(dirname(dirname(dirname(__file__))), """src"""))
sys.path.insert(1, git_repo_path)


# silence FutureWarning warnings in tests since often we can't act on them until
# they become normal warnings - i.e. the tests still need to test the current functionality
warnings.simplefilter(action="""ignore""", category=FutureWarning)



def      _a     (   __UpperCamelCase       :  Tuple    ):
			from transformers.testing_utils import pytest_addoption_shared

			pytest_addoption_shared(__UpperCamelCase    )



def      _a     (   __UpperCamelCase       :  int    ):
			from transformers.testing_utils import pytest_terminal_summary_main

			lowerCAmelCase__ :    int				      =			terminalreporter.config.getoption('''--make-reports'''    )
			if make_reports:
						pytest_terminal_summary_main(__UpperCamelCase	,id=__UpperCamelCase    )



