



"""simple docstring"""






from __future__ import annotations

from collections.abc import Iterable

class 			__SCREAMING_SNAKE_CASE      :


					'''simple docstring'''





					def __init__(			self				:    int,    lowerCamelCase				:    Tuple,    lowerCamelCase				:    Any	)->   List[Any]:
								lowerCamelCase__      ,  lowerCamelCase__						:						Tuple						      =float(lowerCamelCase	), float(lowerCamelCase	)



					def __eq__(			self				:    Dict,    lowerCamelCase				:    List[Any]	)->   Dict:
								return self.x == other.x and self.y == other.y



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



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



					def __lt__(			self				:    Union[str, Any],    lowerCamelCase				:    str	)->   str:
								return not self > other



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



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



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




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






def 	snake_case__  (						__lowerCamelCase							:       list[Point] | list[list[float]] | Iterable[list[float]]				,						):
			"""simple docstring"""
			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 	snake_case__  (						__lowerCamelCase							:       list[Point] | list[list[float]]      ):
			"""simple docstring"""

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

			if not points:
						lowerCamelCase__						:						Any						      =f'''Expecting a list of points but got {points}'''
						raise ValueError(__lowerCamelCase      )

			return _construct_points(__lowerCamelCase      )






def 	snake_case__  (						__lowerCamelCase							:       Point				,						__lowerCamelCase							:       Point				,						__lowerCamelCase							:       Point      ):
			"""simple docstring"""
			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 	snake_case__  (						__lowerCamelCase							:       list[Point]      ):
			"""simple docstring"""
			lowerCamelCase__						:						List[Any]						      =sorted(_validate_input(__lowerCamelCase      )      )
			lowerCamelCase__						:						List[Any]						      =len(__lowerCamelCase      )
			lowerCamelCase__						:						Union[str, Any]						      =set()

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

															if det_k > 0:
																		lowerCamelCase__						:						Optional[Any]						      =True
															elif det_k < 0:
																		lowerCamelCase__						:						Union[str, 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[str]						      =False
																					break

												if points_left_of_ij and points_right_of_ij:
															lowerCamelCase__						:						Tuple						      =False
															break

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

			return sorted(__lowerCamelCase      )






def 	snake_case__  (						__lowerCamelCase							:       list[Point]      ):
			"""simple docstring"""
			lowerCamelCase__						:						str						      =sorted(_validate_input(__lowerCamelCase      )      )
			lowerCamelCase__						:						List[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__						:						Dict						      =points[0]
			lowerCamelCase__						:						Union[str, Any]						      =points[n - 1]

			lowerCamelCase__						:						Dict						      ={left_most_point, right_most_point}
			lowerCamelCase__						:						Optional[Any]						      =[]
			lowerCamelCase__						:						List[Any]						      =[]

			for i in range(1				,						n - 1      ):
						lowerCamelCase__						:						Union[str, Any]						      =_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 	snake_case__  (						__lowerCamelCase							:       list[Point]				,						__lowerCamelCase							:       Point				,						__lowerCamelCase							:       Point				,						__lowerCamelCase							:       set[Point]      ):
			"""simple docstring"""
			if points:
						lowerCamelCase__						:						str						      =None
						lowerCamelCase__						:						Union[str, Any]						      =float('''-inf'''      )
						lowerCamelCase__						:						Optional[Any]						      =[]

						for p in points:
									lowerCamelCase__						:						Any						      =_det(__lowerCamelCase				,						__lowerCamelCase				,						__lowerCamelCase      )

									if det > 0:
												candidate_points.append(__lowerCamelCase      )

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

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






def 	snake_case__  (						__lowerCamelCase							:       list[Point]      ):
			"""simple docstring"""
			lowerCamelCase__						:						Dict						      =sorted(_validate_input(__lowerCamelCase      )      )
			lowerCamelCase__						:						str						      =len(__lowerCamelCase      )

			lowerCamelCase__						:						Union[str, Any]						      =points[:2]
			for i in range(2				,						__lowerCamelCase      ):
						lowerCamelCase__						:						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:
									lowerCamelCase__						:						Any						      =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 	snake_case__  (						):
			"""simple docstring"""
			lowerCamelCase__						:						List[str]						      =[
			    (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__						:						Optional[int]						      =convex_hull_bf(__lowerCamelCase      )

			lowerCamelCase__						:						Any						      =convex_hull_recursive(__lowerCamelCase      )
			assert results_bf == results_recursive

			lowerCamelCase__						:						int						      =convex_hull_melkman(__lowerCamelCase      )
			assert results_bf == results_melkman

			print(__lowerCamelCase      )


if __name__ == "__main__":
		main()





import hashlib
import importlib.util
import json
import os
import pathlib
from types import ModuleType

import pytest
import requests

__lowerCamelCase     :					Optional[Any]				  =						pathlib.Path.cwd().joinpath('''project_euler''')
__lowerCamelCase     :					Dict				  =						pathlib.Path.cwd().joinpath(
    '''scripts''', '''project_euler_answers.json'''
)

with open(PROJECT_EULER_ANSWERS_PATH) as file_handle:
   __lowerCamelCase     :					dict[str, str]				  =						json.load(file_handle)



def       __SCREAMING_SNAKE_CASE    (   __UpperCamelCase       :			pathlib.Path      )				->   ModuleType:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__     				= importlib.util.spec_from_file_location(file_path.name					,	str(__UpperCamelCase      )      )
  SCREAMING_SNAKE_CASE__     				= importlib.util.module_from_spec(__UpperCamelCase      )  # type: ignore
  spec.loader.exec_module(__UpperCamelCase      )  # type: ignore
  return module



def       __SCREAMING_SNAKE_CASE    (   )				->   list[pathlib.Path]:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__     				= []
  for problem_dir_path in PROJECT_EULER_DIR_PATH.iterdir():
    if problem_dir_path.is_file() or problem_dir_path.name.startswith("""_"""      ):
      continue
    for file_path in problem_dir_path.iterdir():
      if file_path.suffix != ".py" or file_path.name.startswith(("""_""", """test""")      ):
        continue
      solution_file_paths.append(__UpperCamelCase      )
  return solution_file_paths



def       __SCREAMING_SNAKE_CASE    (   )				->   str:







  """simple docstring"""





  with open(os.environ["""GITHUB_EVENT_PATH"""]      ) as file:
    SCREAMING_SNAKE_CASE__     				= json.load(__UpperCamelCase      )
  return event["pull_request"]["url"] + "/files"



def       __SCREAMING_SNAKE_CASE    (   )				->   list[pathlib.Path]:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__     				= []
  SCREAMING_SNAKE_CASE__     				= {
      """Accept""": """application/vnd.github.v3+json""",
      """Authorization""": """token """ + os.environ["""GITHUB_TOKEN"""],
  }
  SCREAMING_SNAKE_CASE__     				= requests.get(get_files_url()					,	headers=__UpperCamelCase      ).json()
  for file in files:
    SCREAMING_SNAKE_CASE__     				= pathlib.Path.cwd().joinpath(file["""filename"""]      )
    if (
        filepath.suffix != ".py"
        or filepath.name.startswith(("""_""", """test""")      )
        or not filepath.name.startswith("""sol"""      )
    ):
      continue
    solution_file_paths.append(__UpperCamelCase      )
  return solution_file_paths



def       __SCREAMING_SNAKE_CASE    (   )				->   list[pathlib.Path]:







  """simple docstring"""





  if os.environ.get("""CI"""      ) and os.environ.get("""GITHUB_EVENT_NAME"""      ) == "pull_request":
    # Return only if there are any, otherwise default to all solutions
    if filepaths := added_solution_file_path():
      return filepaths
  return all_solution_file_paths()






@pytest.mark.parametrize(
    """solution_path"""					,	collect_solution_file_paths()					,	ids=lambda __UpperCamelCase      : f"""{path.parent.name}/{path.name}"""					,	)
def       __SCREAMING_SNAKE_CASE    (   __UpperCamelCase       :			pathlib.Path      )				->   None:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__     				= solution_path.parent.name[8:].zfill(3      )
  SCREAMING_SNAKE_CASE__     				= PROBLEM_ANSWERS[problem_number]
  SCREAMING_SNAKE_CASE__     				= convert_path_to_module(__UpperCamelCase      )
  SCREAMING_SNAKE_CASE__     				= str(solution_module.solution()      )  # type: ignore
  SCREAMING_SNAKE_CASE__     				= hashlib.shaaaa(answer.encode()      ).hexdigest()
  assert (
      answer == expected
  ), f"""Expected solution to {problem_number} to have hash {expected}, got {answer}"""
