


from __future__ import annotations

from collections.abc import Iterable





class     __a     :
 def __init__(  self							,					lowerCAmelCase__							,					lowerCAmelCase__					)   ->							Optional[Any]:




        '''simple docstring'''
        lowercase__     ,		lowercase__:  Optional[Any]         =  float(__lowercase					), float(__lowercase					)
 def __eq__(  self							,					lowerCAmelCase__					)   ->							str:




        '''simple docstring'''
        return self.x == other.x and self.y == other.y
 def __ne__(  self							,					lowerCAmelCase__					)   ->							Any:




        '''simple docstring'''
        return not self == other
 def __gt__(  self							,					lowerCAmelCase__					)   ->							Tuple:




        '''simple docstring'''
        if self.x > other.x:
               return True
        elif self.x == other.x:
               return self.y > other.y
        return False
 def __lt__(  self							,					lowerCAmelCase__					)   ->							Tuple:




        '''simple docstring'''
        return not self > other
 def __ge__(  self							,					lowerCAmelCase__					)   ->							Optional[Any]:




        '''simple docstring'''
        if self.x > other.x:
               return True
        elif self.x == other.x:
               return self.y >= other.y
        return False
 def __le__(  self							,					lowerCAmelCase__					)   ->							Optional[int]:




        '''simple docstring'''
        if self.x < other.x:
               return True
        elif self.x == other.x:
               return self.y <= other.y
        return False
 def __repr__(  self					)   ->							str:




        '''simple docstring'''
        return F'({self.x}, {self.y})'
 def __hash__(  self					)   ->							List[str]:




        '''simple docstring'''
        return hash(self.x					)





def   snake_case_	(    snake_case     ,				)    ->							list[Point]:
       lowercase__:  List[str]         =  []
       if list_of_tuples:
              for p in list_of_tuples:
                     if isinstance(_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE	):
                            points.append(_SCREAMING_SNAKE_CASE	)
                     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_	(    snake_case	)    ->							list[Point]:

       if not hasattr(_SCREAMING_SNAKE_CASE     ,				'__iter__'	):
              lowercase__:  Optional[int]         =  f'Expecting an iterable object but got an non-iterable type {points}'
              raise ValueError(_SCREAMING_SNAKE_CASE	)

       if not points:
              lowercase__:  str         =  f'Expecting a list of points but got {points}'
              raise ValueError(_SCREAMING_SNAKE_CASE	)

       return _construct_points(_SCREAMING_SNAKE_CASE	)




def   snake_case_	(    snake_case     ,				snake_case     ,				snake_case	)    ->							float:
       lowercase__:  List[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_	(    snake_case	)    ->							list[Point]:
       lowercase__:  Union[str, Any]         =  sorted(_validate_input(_SCREAMING_SNAKE_CASE	)	)
       lowercase__:  Dict         =  len(_SCREAMING_SNAKE_CASE	)
       lowercase__:  Optional[Any]         =  set()

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

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

                            if points_left_of_ij and points_right_of_ij:
                                   lowercase__:  str         =  False
                                   break

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

       return sorted(_SCREAMING_SNAKE_CASE	)




def   snake_case_	(    snake_case	)    ->							list[Point]:
       lowercase__:  str         =  sorted(_validate_input(_SCREAMING_SNAKE_CASE	)	)
       lowercase__:  List[Any]         =  len(_SCREAMING_SNAKE_CASE	)

       # 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__:  Optional[Any]         =  points[0]
       lowercase__:  Union[str, Any]         =  points[n - 1]

       lowercase__:  Any         =  {left_most_point, right_most_point}
       lowercase__:  Optional[int]         =  []
       lowercase__:  Union[str, Any]         =  []

       for i in range(1     ,				n - 1	):
              lowercase__:  Optional[Any]         =  _det(_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE     ,				points[i]	)

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

       _construct_hull(_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE	)
       _construct_hull(_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE	)

       return sorted(_SCREAMING_SNAKE_CASE	)




def   snake_case_	(    snake_case     ,				snake_case     ,				snake_case     ,				snake_case	)    ->							None:
       if points:
              lowercase__:  Optional[Any]         =  None
              lowercase__:  Any         =  float('-inf'	)
              lowercase__:  str         =  []

              for p in points:
                     lowercase__:  List[Any]         =  _det(_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE     ,				_SCREAMING_SNAKE_CASE	)

                     if det > 0:
                            candidate_points.append(_SCREAMING_SNAKE_CASE	)

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

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




def   snake_case_	(    snake_case	)    ->							list[Point]:
       lowercase__:  List[Any]         =  sorted(_validate_input(_SCREAMING_SNAKE_CASE	)	)
       lowercase__:  Union[str, Any]         =  len(_SCREAMING_SNAKE_CASE	)

       lowercase__:  Tuple         =  points[:2]
       for i in range(2     ,				_SCREAMING_SNAKE_CASE	):
              lowercase__:  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:
                     lowercase__:  Union[str, Any]         =  points[i]
       i += 1

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




def   snake_case_	(    )    ->							Union[str, Any]:
       lowercase__:  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)]
       lowercase__:  Any         =  convex_hull_bf(_SCREAMING_SNAKE_CASE	)

       lowercase__:  Optional[Any]         =  convex_hull_recursive(_SCREAMING_SNAKE_CASE	)
       assert results_bf == results_recursive

       lowercase__:  int         =  convex_hull_melkman(_SCREAMING_SNAKE_CASE	)
       assert results_bf == results_melkman

       print(_SCREAMING_SNAKE_CASE	)


if __name__ == "__main__":
 main()










"""simple docstring"""



from __future__ import annotations

from math import pi, pow




def       snake_case__		(   _SCREAMING_SNAKE_CASE			)    ->float:
 if side_length < 0:
  raise ValueError("""vol_cube() only accepts non-negative values"""			)
 return pow(_SCREAMING_SNAKE_CASE       ,	3			)




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 if height < 0 or radius < 0:
  raise ValueError("""vol_spherical_cap() only accepts non-negative values"""			)
 # Volume is 1/3 pi * height squared * (3 * radius - height)
 return 1 / 3 * pi * pow(_SCREAMING_SNAKE_CASE       ,	2			) * (3 * radius - height)




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 if radius_a < 0 or radius_a < 0 or centers_distance < 0:
  raise ValueError("""vol_spheres_intersect() only accepts non-negative values"""			)
 if centers_distance == 0:
  return vol_sphere(min(_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)			)

 UpperCAmelCase__ 						=				(
     (radius_a - radius_a + centers_distance)
     * (radius_a + radius_a - centers_distance)
     / (2 * centers_distance)
 )
 UpperCAmelCase__ 						=				(
     (radius_a - radius_a + centers_distance)
     * (radius_a + radius_a - centers_distance)
     / (2 * centers_distance)
 )

 return vol_spherical_cap(_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			) + vol_spherical_cap(_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:

 if radius_a <= 0 or radius_a <= 0 or centers_distance < 0:
  raise ValueError(
      """vol_spheres_union() only accepts non-negative values, non-zero radius"""			)

 if centers_distance == 0:
  return vol_sphere(max(_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)			)

 return (
     vol_sphere(_SCREAMING_SNAKE_CASE			)
     + vol_sphere(_SCREAMING_SNAKE_CASE			)
     - vol_spheres_intersect(_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)
 )




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 if width < 0 or height < 0 or length < 0:
  raise ValueError("""vol_cuboid() only accepts non-negative values"""			)
 return float(width * height * length			)




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 if height < 0 or area_of_base < 0:
  raise ValueError("""vol_cone() only accepts non-negative values"""			)
 return area_of_base * height / 3.0




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 if height < 0 or radius < 0:
  raise ValueError("""vol_right_circ_cone() only accepts non-negative values"""			)
 return pi * pow(_SCREAMING_SNAKE_CASE       ,	2			) * height / 3.0




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 if height < 0 or area_of_base < 0:
  raise ValueError("""vol_prism() only accepts non-negative values"""			)
 return float(area_of_base * height			)




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 if height < 0 or area_of_base < 0:
  raise ValueError("""vol_pyramid() only accepts non-negative values"""			)
 return area_of_base * height / 3.0




def       snake_case__		(   _SCREAMING_SNAKE_CASE			)    ->float:
 if radius < 0:
  raise ValueError("""vol_sphere() only accepts non-negative values"""			)
 # Volume is 4/3 * pi * radius cubed
 return 4 / 3 * pi * pow(_SCREAMING_SNAKE_CASE       ,	3			)




def       snake_case__		(   _SCREAMING_SNAKE_CASE			)    ->float:
 if radius < 0:
  raise ValueError("""vol_hemisphere() only accepts non-negative values"""			)
 # Volume is radius cubed * pi * 2/3
 return pow(_SCREAMING_SNAKE_CASE       ,	3			) * pi * 2 / 3




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 if height < 0 or radius < 0:
  raise ValueError("""vol_circular_cylinder() only accepts non-negative values"""			)
 # Volume is radius squared * height * pi
 return pow(_SCREAMING_SNAKE_CASE       ,	2			) * height * pi




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 # Volume - (outer_radius squared - inner_radius squared) * pi * height
 if inner_radius < 0 or outer_radius < 0 or height < 0:
  raise ValueError(
      """vol_hollow_circular_cylinder() only accepts non-negative values"""			)
 if outer_radius <= inner_radius:
  raise ValueError("""outer_radius must be greater than inner_radius"""			)
 return pi * (pow(_SCREAMING_SNAKE_CASE       ,	2			) - pow(_SCREAMING_SNAKE_CASE       ,	2			)) * height




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 # Volume is 1/3 * pi * height *
 #           (radius_1 squared + radius_2 squared + radius_1 * radius_2)
 if radius_a < 0 or radius_a < 0 or height < 0:
  raise ValueError("""vol_conical_frustum() only accepts non-negative values"""			)
 return (
     1
     / 3
     * pi
     * height
     * (pow(_SCREAMING_SNAKE_CASE       ,	2			) + pow(_SCREAMING_SNAKE_CASE       ,	2			) + radius_a * radius_a)
 )




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->float:
 if torus_radius < 0 or tube_radius < 0:
  raise ValueError("""vol_torus() only accepts non-negative values"""			)
 return 2 * pow(_SCREAMING_SNAKE_CASE       ,	2			) * torus_radius * pow(_SCREAMING_SNAKE_CASE       ,	2			)




def       snake_case__		(   )    ->str:
 print("""Volumes:"""			)
 print(F'''Cube: {vol_cube(2			) = }'''			)  # = 8
 print(F'''Cuboid: {vol_cuboid(2       ,	2       ,	2			) = }'''			)  # = 8
 print(F'''Cone: {vol_cone(2       ,	2			) = }'''			)  # ~= 1.33
 print(F'''Right Circular Cone: {vol_right_circ_cone(2       ,	2			) = }'''			)  # ~= 8.38
 print(F'''Prism: {vol_prism(2       ,	2			) = }'''			)  # = 4
 print(F'''Pyramid: {vol_pyramid(2       ,	2			) = }'''			)  # ~= 1.33
 print(F'''Sphere: {vol_sphere(2			) = }'''			)  # ~= 33.5
 print(F'''Hemisphere: {vol_hemisphere(2			) = }'''			)  # ~= 16.75
 print(F'''Circular Cylinder: {vol_circular_cylinder(2       ,	2			) = }'''			)  # ~= 25.1
 print(F'''Torus: {vol_torus(2       ,	2			) = }'''			)  # ~= 157.9
 print(F'''Conical Frustum: {vol_conical_frustum(2       ,	2       ,	4			) = }'''			)  # ~= 58.6
 print(F'''Spherical cap: {vol_spherical_cap(1       ,	2			) = }'''			)  # ~= 5.24
 print(F'''Spheres intersetion: {vol_spheres_intersect(2       ,	2       ,	1			) = }'''			)  # ~= 21.21
 print(F'''Spheres union: {vol_spheres_union(2       ,	2       ,	1			) = }'''			)  # ~= 45.81
 print(
     F'''Hollow Circular Cylinder: {vol_hollow_circular_cylinder(1       ,	2       ,	3			) = }'''			)  # ~= 28.3


if __name__ == "__main__":
 main()



