




"""simple docstring"""




from __future__ import annotations

from collections.abc import Iterable

class        UpperCAmelCase_  :
		def __init__(		self							,		UpperCamelCase_							,		UpperCamelCase_   )		->   str:
					__lowercase	,__lowercase	:       List[str]				=   float(UpperCamelCase_   ), float(UpperCamelCase_   )
		def __eq__(		self							,		UpperCamelCase_   )		->   Dict:
					return self.x == other.x and self.y == other.y
		def __ne__(		self							,		UpperCamelCase_   )		->   Dict:
					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_   )		->   List[Any]:
					return not self > other
		def __ge__(		self							,		UpperCamelCase_   )		->   Any:
					if self.x > other.x:
								return True
					elif self.x == other.x:
								return self.y >= other.y
					return False
		def __le__(		self							,		UpperCamelCase_   )		->   int:
					if self.x < other.x:
								return True
					elif self.x == other.x:
								return self.y <= other.y
					return False
		def __repr__(		self   )		->   Optional[Any]:
					return F"""({self.x}, {self.y})"""
		def __hash__(		self   )		->   List[Any]:
					return hash(self.x   )







def       __UpperCAmelCase      (				__UpperCamelCase					,							):
			__lowercase	:       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       __UpperCAmelCase      (				__UpperCamelCase					):

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

			if not points:
						__lowercase	:       Optional[int]				=   f"""Expecting a list of points but got {points}"""
						raise ValueError(__UpperCamelCase					)

			return _construct_points(__UpperCamelCase					)







def       __UpperCAmelCase      (				__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase					):
			__lowercase	:       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       __UpperCAmelCase      (				__UpperCamelCase					):
			__lowercase	:       Optional[int]				=   sorted(_validate_input(__UpperCamelCase					)					)
			__lowercase	:       Optional[int]				=   len(__UpperCamelCase					)
			__lowercase	:       Tuple				=   set()

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

															if det_k > 0:
																		__lowercase	:       Tuple				=   True
															elif det_k < 0:
																		__lowercase	:       Tuple				=   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]:
																					__lowercase	:       int				=   False
																					break

												if points_left_of_ij and points_right_of_ij:
															__lowercase	:       Tuple				=   False
															break

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

			return sorted(__UpperCamelCase					)







def       __UpperCAmelCase      (				__UpperCamelCase					):
			__lowercase	:       List[Any]				=   sorted(_validate_input(__UpperCamelCase					)					)
			__lowercase	:       Tuple				=   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

			__lowercase	:       Tuple				=   points[0]
			__lowercase	:       Dict				=   points[n - 1]

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

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

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

									if det > 0:
												candidate_points.append(__UpperCamelCase					)

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

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







def       __UpperCAmelCase      (				__UpperCamelCase					):
			__lowercase	:       Union[str, Any]				=   sorted(_validate_input(__UpperCamelCase					)					)
			__lowercase	:       Optional[Any]				=   len(__UpperCamelCase					)

			__lowercase	:       Tuple				=   points[:2]
			for i in range(2					,							__UpperCamelCase					):
						__lowercase	:       List[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:
									__lowercase	:       Any				=   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       __UpperCAmelCase      (				):
			__lowercase	:       Tuple				=   [
			    (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)]
			__lowercase	:       List[str]				=   convex_hull_bf(__UpperCamelCase					)

			__lowercase	:       Tuple				=   convex_hull_recursive(__UpperCamelCase					)
			assert results_bf == results_recursive

			__lowercase	:       Union[str, Any]				=   convex_hull_melkman(__UpperCamelCase					)
			assert results_bf == results_melkman

			print(__UpperCamelCase					)


if __name__ == "__main__":
			main()









"""simple docstring"""




from __future__ import annotations

import random

from matplotlib import animation
from matplotlib import pyplot as plt

# Frame rate of the animation
a_            =   2_0

# Time between time steps in seconds
a_            =   INTERVAL / 1_0_0_0

class        UpperCAmelCase_  :
		def __init__(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_ = 1.0							,		UpperCamelCase_ = 1.0							,		UpperCamelCase_ = "blue"							,		)		->   None:
					__lowercase	:       Optional[int]				=   position_x
					__lowercase	:       List[Any]				=   position_y
					__lowercase	:       Optional[int]				=   velocity_x
					__lowercase	:       List[str]				=   velocity_y
					__lowercase	:       List[Any]				=   mass
					__lowercase	:       Tuple				=   size
					__lowercase	:       Tuple				=   color
		@property
		def 					_lowerCamelCase    (		self   )		->   tuple[float, float]:
					return self.position_x, self.position_y
		@property
		def 					_lowerCamelCase    (		self   )		->   tuple[float, float]:
					return self.velocity_x, self.velocity_y
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_   )		->   None:
					self.velocity_x += force_x * delta_time
					self.velocity_y += force_y * delta_time
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_   )		->   None:
					self.position_x += self.velocity_x * delta_time
					self.position_y += self.velocity_y * delta_time


class        UpperCAmelCase_  :
		def __init__(		self							,		UpperCamelCase_							,		UpperCamelCase_ = 1.0							,		UpperCamelCase_ = 1.0							,		UpperCamelCase_ = 0.0							,		)		->   None:
					__lowercase	:       int				=   bodies
					__lowercase	:       Dict				=   gravitation_constant
					__lowercase	:       List[Any]				=   time_factor
					__lowercase	:       List[str]				=   softening_factor
		def __len__(		self   )		->   int:
					return len(self.bodies   )
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_   )		->   None:
					for bodya in self.bodies:
								__lowercase	:       Optional[Any]				=   0.0
								__lowercase	:       Any				=   0.0
								for bodya in self.bodies:
											if bodya != bodya:
														__lowercase	:       Union[str, Any]				=   bodya.position_x - bodya.position_x
														__lowercase	:       str				=   bodya.position_y - bodya.position_y

														# Calculation of the distance using Pythagoras's theorem
														# Extra factor due to the softening technique
														__lowercase	:       str				=   (dif_x**2 + dif_y**2 + self.softening_factor) ** (
														    1 / 2
														)

														# Newton's law of universal gravitation.
														force_x += (
														    self.gravitation_constant * bodya.mass * dif_x / distance**3
														)
														force_y += (
														    self.gravitation_constant * bodya.mass * dif_y / distance**3
														)

            # Update the body's velocity once all the force components have been added
								bodya.update_velocity(UpperCamelCase_							,		UpperCamelCase_							,		delta_time * self.time_factor   )

					# Update the positions only after all the velocities have been updated
					for body in self.bodies:
								body.update_position(delta_time * self.time_factor   )







def       __UpperCAmelCase      (				__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase					):
			body_system.update_system(__UpperCamelCase					)

			# Update the positions of the patches
			for patch, body in zip(__UpperCamelCase					,							body_system.bodies					):
						__lowercase	:       List[str]				=   (body.position_x, body.position_y)







def       __UpperCAmelCase      (				__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase = -1					,							__UpperCamelCase = 1					,							__UpperCamelCase = -1					,							__UpperCamelCase = 1					,							):
			__lowercase	:       List[str]				=   plt.figure()
			fig.canvas.set_window_title(__UpperCamelCase					)
			__lowercase	:       List[Any]				=   plt.axes(
			    xlim=(x_start, x_end)					,							ylim=(y_start, y_end)					)  # Set section to be plotted
			plt.gca().set_aspect('''equal'''					)  # Fix aspect ratio

			# Each body is drawn as a patch by the plt-function
			__lowercase	:       Any				=   [
			    plt.Circle((body.position_x, body.position_y)					,							body.size					,							fc=body.color					)
			    for body in body_system.bodies
			]

			for patch in patches:
						ax.add_patch(__UpperCamelCase					)

			# Function called at each step of the animation
			def update(__UpperCamelCase					) -> list[plt.Circle]:
						update_step(__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase					)
						return patches

			__lowercase	:       Tuple				=   animation.FuncAnimation(  # noqa: F841
			    __UpperCamelCase					,							__UpperCamelCase					,							interval=__UpperCamelCase					,							blit=__UpperCamelCase					)

			plt.show()







def       __UpperCAmelCase      (				):
			__lowercase	:       Dict				=   0.9_700_436
			__lowercase	:       Tuple				=   -0.24_308_753
			__lowercase	:       Any				=   0.466_203_685
			__lowercase	:       str				=   0.43_236_573

			__lowercase	:       int				=   [
			    Body(__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase					,							size=0.2					,							color='''red'''					),
			    Body(-position_x					,							-position_y					,							__UpperCamelCase					,							__UpperCamelCase					,							size=0.2					,							color='''green'''					),
			    Body(0					,							0					,							-2 * velocity_x					,							-2 * velocity_y					,							size=0.2					,							color='''blue'''					),
			]
			return BodySystem(__UpperCamelCase					,							time_factor=3					)







def       __UpperCAmelCase      (				):
			__lowercase	:       Tuple				=   7.3_476e22
			__lowercase	:       Optional[int]				=   5.972e24
			__lowercase	:       str				=   10_22
			__lowercase	:       Any				=   3_84_39_90_00
			__lowercase	:       Optional[int]				=   6.674e-11

			# Calculation of the respective velocities so that total impulse is zero,
			# i.e. the two bodies together don't move
			__lowercase	:       Optional[Any]				=   earth_mass * velocity_dif / (earth_mass + moon_mass)
			__lowercase	:       Tuple				=   moon_velocity - velocity_dif

			__lowercase	:       Tuple				=   Body(-earth_moon_distance					,							0					,							0					,							__UpperCamelCase					,							__UpperCamelCase					,							10_00_00_00					,							'''grey'''					)
			__lowercase	:       Dict				=   Body(0					,							0					,							0					,							__UpperCamelCase					,							__UpperCamelCase					,							50_00_00_00					,							'''blue'''					)
			return BodySystem([earth, moon]					,							__UpperCamelCase					,							time_factor=1_00_00_00					)







def       __UpperCAmelCase      (				):
			__lowercase	:       Optional[Any]				=   []
			for _ in range(10					):
						__lowercase	:       str				=   random.uniform(-0.5					,							0.5					)
						__lowercase	:       int				=   random.uniform(-0.5					,							0.5					)

						# Bodies are created pairwise with opposite velocities so that the
						# total impulse remains zero
						bodies.append(
						    Body(
						        random.uniform(-0.5					,							0.5					)					,							random.uniform(-0.5					,							0.5					)					,							__UpperCamelCase					,							__UpperCamelCase					,							size=0.05					,							)					)
						bodies.append(
						    Body(
						        random.uniform(-0.5					,							0.5					)					,							random.uniform(-0.5					,							0.5					)					,							-velocity_x					,							-velocity_y					,							size=0.05					,							)					)
			return BodySystem(__UpperCamelCase					,							0.01					,							10					,							0.1					)


if __name__ == "__main__":
			plot('Figure-8 solution to the 3-body-problem', example_a(), -2, 2, -2, 2)
			plot(
			    'Moon\'s orbit around the earth',
			    example_a(),
			    -4_3_0_0_0_0_0_0_0,
			    4_3_0_0_0_0_0_0_0,
			    -4_3_0_0_0_0_0_0_0,
			    4_3_0_0_0_0_0_0_0,
			)
			plot('Random system with many bodies', example_a(), -1.5, 1.5, -1.5, 1.5)



