





import numpy as np

class 						UpperCamelCase__					:



     '''simple docstring'''

     def __init__(				self		:       Optional[int]		,lowerCamelCase__		:       str=5		,lowerCamelCase__		:       Optional[int]=5			)	->						List[str]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		depth
           SCREAMING_SNAKE_CASE						=		0
           SCREAMING_SNAKE_CASE						=		None
           SCREAMING_SNAKE_CASE						=		None
           SCREAMING_SNAKE_CASE						=		min_leaf_size
           SCREAMING_SNAKE_CASE						=		None






     def 							SCREAMING_SNAKE_CASE__    (				self		:       List[str]		,lowerCamelCase__		:       str		,lowerCamelCase__		:       Union[str, Any]			)	->						str:




           '''simple docstring'''


           if labels.ndim != 1:
                 print("""Error: Input labels must be one dimensional"""			)

           return np.mean((labels - prediction) ** 2			)






     def 							SCREAMING_SNAKE_CASE__    (				self		:       Dict		,lowerCamelCase__		:       List[Any]		,lowerCamelCase__		:       str			)	->						str:




           '''simple docstring'''


           if x.ndim != 1:
                 print("""Error: Input data set must be one dimensional"""			)
                 return
           if len(lowerCamelCase__			) != len(lowerCamelCase__			):
                 print("""Error: X and y have different lengths"""			)
                 return
           if y.ndim != 1:
                 print("""Error: Data set labels must be one dimensional"""			)
                 return

           if len(lowerCamelCase__			) < 2 * self.min_leaf_size:
                 SCREAMING_SNAKE_CASE						=		np.mean(lowerCamelCase__			)
                 return

           if self.depth == 1:
                 SCREAMING_SNAKE_CASE						=		np.mean(lowerCamelCase__			)
                 return

           SCREAMING_SNAKE_CASE						=		0
           SCREAMING_SNAKE_CASE						=		self.mean_squared_error(lowerCamelCase__		,np.mean(lowerCamelCase__			)			) * 2
           for i in range(len(lowerCamelCase__			)			):
                 if len(x[:i]			) < self.min_leaf_size:
                       continue
                 elif len(x[i:]			) < self.min_leaf_size:
                       continue
                 else:
                       SCREAMING_SNAKE_CASE						=		self.mean_squared_error(x[:i]		,np.mean(y[:i]			)			)
                       SCREAMING_SNAKE_CASE						=		self.mean_squared_error(x[i:]		,np.mean(y[i:]			)			)
                       SCREAMING_SNAKE_CASE						=		error_left + error_right
                       if error < min_error:
                             SCREAMING_SNAKE_CASE						=		i
                             SCREAMING_SNAKE_CASE						=		error

           if best_split != 0:
                 SCREAMING_SNAKE_CASE						=		x[:best_split]
                 SCREAMING_SNAKE_CASE						=		y[:best_split]
                 SCREAMING_SNAKE_CASE						=		x[best_split:]
                 SCREAMING_SNAKE_CASE						=		y[best_split:]

                 SCREAMING_SNAKE_CASE						=		x[best_split]
                 SCREAMING_SNAKE_CASE						=		DecisionTree(
                     depth=self.depth - 1		,min_leaf_size=self.min_leaf_size			)
                 SCREAMING_SNAKE_CASE						=		DecisionTree(
                     depth=self.depth - 1		,min_leaf_size=self.min_leaf_size			)
                 self.left.train(lowerCamelCase__		,lowerCamelCase__			)
                 self.right.train(lowerCamelCase__		,lowerCamelCase__			)
           else:
                 SCREAMING_SNAKE_CASE						=		np.mean(lowerCamelCase__			)

           return






     def 							SCREAMING_SNAKE_CASE__    (				self		:       Tuple		,lowerCamelCase__		:       Union[str, Any]			)	->						Optional[Any]:




           '''simple docstring'''


           if self.prediction is not None:
                 return self.prediction
           elif self.left or self.right is not None:
                 if x >= self.decision_boundary:
                       return self.right.predict(lowerCamelCase__			)
                 else:
                       return self.left.predict(lowerCamelCase__			)
           else:
                 print("""Error: Decision tree not yet trained"""			)
                 return None

class 						UpperCamelCase__					:



     '''simple docstring'''

     @staticmethod
     def 							SCREAMING_SNAKE_CASE__    (				lowerCamelCase__		:       Optional[int]		,lowerCamelCase__		:       Tuple			)	->						Union[str, Any]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		float(0			)
           for label in labels:
                 squared_error_sum += (label - prediction) ** 2

           return float(squared_error_sum / labels.size			)



def   __lowercase  ( )					->  int:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		np.arange(-1.0					,		1.0					,		0.005      )
      SCREAMING_SNAKE_CASE						=		np.sin(_SCREAMING_SNAKE_CASE      )

      SCREAMING_SNAKE_CASE						=		DecisionTree(depth=10					,		min_leaf_size=10      )
      tree.train(_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      )

      SCREAMING_SNAKE_CASE						=		(np.random.rand(10      ) * 2) - 1
      SCREAMING_SNAKE_CASE						=		np.array([tree.predict(_SCREAMING_SNAKE_CASE      ) for x in test_cases]      )
      SCREAMING_SNAKE_CASE						=		np.mean((predictions - test_cases) ** 2      )

      print("""Test values: """ + str(_SCREAMING_SNAKE_CASE      )      )
      print("""Predictions: """ + str(_SCREAMING_SNAKE_CASE      )      )
      print("""Average error: """ + str(_SCREAMING_SNAKE_CASE      )      )


if __name__ == "__main__":
      main()
      import doctest

      doctest.testmod(name="""mean_squarred_error""", verbose=True)









from __future__ import annotations

from collections.abc import Iterable

class 						UpperCamelCase__					:



     '''simple docstring'''

     def __init__(				self		:       Optional[Any]		,lowerCamelCase__		:       Optional[int]		,lowerCamelCase__		:       List[Any]			)	->						int:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE,   SCREAMING_SNAKE_CASE						=		float(lowerCamelCase__			), float(lowerCamelCase__			)






     def __eq__(				self		:       int		,lowerCamelCase__		:       Union[str, Any]			)	->						List[str]:




           '''simple docstring'''


           return self.x == other.x and self.y == other.y






     def __ne__(				self		:       Optional[int]		,lowerCamelCase__		:       int			)	->						Dict:




           '''simple docstring'''


           return not self == other






     def __gt__(				self		:       Optional[Any]		,lowerCamelCase__		:       Optional[Any]			)	->						List[Any]:




           '''simple docstring'''


           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__		:       Optional[Any]			)	->						Optional[Any]:




           '''simple docstring'''


           return not self > other






     def __ge__(				self		:       Optional[Any]		,lowerCamelCase__		:       Tuple			)	->						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		:       Tuple		,lowerCamelCase__		:       int			)	->						Dict:




           '''simple docstring'''


           if self.x < other.x:
                 return True
           elif self.x == other.x:
                 return self.y <= other.y
           return False






     def __repr__(				self		:       Dict			)	->						Any:




           '''simple docstring'''


           return F"""({self.x}, {self.y})"""






     def __hash__(				self		:       List[Any]			)	->						List[Any]:




           '''simple docstring'''


           return hash(self.x			)



def   __lowercase  ( _SCREAMING_SNAKE_CASE					,		)					->  list[Point]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		[]
      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   __lowercase  ( _SCREAMING_SNAKE_CASE      )					->  list[Point]:


      '''simple docstring'''


      if not hasattr(_SCREAMING_SNAKE_CASE					,		"""__iter__"""      ):
            SCREAMING_SNAKE_CASE						=		F"""Expecting an iterable object but got an non-iterable type {points}"""
            raise ValueError(_SCREAMING_SNAKE_CASE      )

      if not points:
            SCREAMING_SNAKE_CASE						=		F"""Expecting a list of points but got {points}"""
            raise ValueError(_SCREAMING_SNAKE_CASE      )

      return _construct_points(_SCREAMING_SNAKE_CASE      )



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


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		(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   __lowercase  ( _SCREAMING_SNAKE_CASE      )					->  list[Point]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		sorted(_validate_input(_SCREAMING_SNAKE_CASE      )      )
      SCREAMING_SNAKE_CASE						=		len(_SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE						=		set()

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

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

                        if points_left_of_ij and points_right_of_ij:
                              SCREAMING_SNAKE_CASE						=		False
                              break

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

      return sorted(_SCREAMING_SNAKE_CASE      )



def   __lowercase  ( _SCREAMING_SNAKE_CASE      )					->  list[Point]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		sorted(_validate_input(_SCREAMING_SNAKE_CASE      )      )
      SCREAMING_SNAKE_CASE						=		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

      SCREAMING_SNAKE_CASE						=		points[0]
      SCREAMING_SNAKE_CASE						=		points[n - 1]

      SCREAMING_SNAKE_CASE						=		{left_most_point, right_most_point}
      SCREAMING_SNAKE_CASE						=		[]
      SCREAMING_SNAKE_CASE						=		[]

      for i in range(1					,		n - 1      ):
            SCREAMING_SNAKE_CASE						=		_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   __lowercase  ( _SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      )					->  None:


      '''simple docstring'''


      if points:
            SCREAMING_SNAKE_CASE						=		None
            SCREAMING_SNAKE_CASE						=		float("""-inf"""      )
            SCREAMING_SNAKE_CASE						=		[]

            for p in points:
                  SCREAMING_SNAKE_CASE						=		_det(_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      )

                  if det > 0:
                        candidate_points.append(_SCREAMING_SNAKE_CASE      )

                        if det > extreme_point_distance:
                              SCREAMING_SNAKE_CASE						=		det
                              SCREAMING_SNAKE_CASE						=		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   __lowercase  ( _SCREAMING_SNAKE_CASE      )					->  list[Point]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		sorted(_validate_input(_SCREAMING_SNAKE_CASE      )      )
      SCREAMING_SNAKE_CASE						=		len(_SCREAMING_SNAKE_CASE      )

      SCREAMING_SNAKE_CASE						=		points[:2]
      for i in range(2					,		_SCREAMING_SNAKE_CASE      ):
            SCREAMING_SNAKE_CASE						=		_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:
                  SCREAMING_SNAKE_CASE						=		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   __lowercase  ( )					->  Any:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		[
          (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)]
      SCREAMING_SNAKE_CASE						=		convex_hull_bf(_SCREAMING_SNAKE_CASE      )

      SCREAMING_SNAKE_CASE						=		convex_hull_recursive(_SCREAMING_SNAKE_CASE      )
      assert results_bf == results_recursive

      SCREAMING_SNAKE_CASE						=		convex_hull_melkman(_SCREAMING_SNAKE_CASE      )
      assert results_bf == results_melkman

      print(_SCREAMING_SNAKE_CASE      )


if __name__ == "__main__":
      main()


