code: 
  
  from __future__ import annotations
  
  from collections.abc import Iterable
  class 					A_   :
  
  
      '''simple docstring'''
  
  
  
  
  
  
      def __init__(self     ,      lowercase__     ,      lowercase__  )     ->      Optional[int]:
          __UpperCAmelCase					,     __UpperCAmelCase									=			float(lowercase__  ), float(lowercase__  )
  
  
      def __eq__(self     ,      lowercase__  )     ->      Optional[Any]:
          return self.x == other.x and self.y == other.y
  
  
      def __ne__(self     ,      lowercase__  )     ->      Any:
          return not self == other
  
  
      def __gt__(self     ,      lowercase__  )     ->      Dict:
          if self.x > other.x:
              return True
          elif self.x == other.x:
              return self.y > other.y
          return False
  
  
      def __lt__(self     ,      lowercase__  )     ->      List[str]:
          return not self > other
  
  
      def __ge__(self     ,      lowercase__  )     ->      Dict:
          if self.x > other.x:
              return True
          elif self.x == other.x:
              return self.y >= other.y
          return False
  
  
      def __le__(self     ,      lowercase__  )     ->      Optional[int]:
          if self.x < other.x:
              return True
          elif self.x == other.x:
              return self.y <= other.y
          return False
  
  
      def __repr__(self  )     ->      List[str]:
          return F'''({self.x}, {self.y})'''
  
  
  
  
  
  
      def __hash__(self  )     ->      List[Any]:
          return hash(self.x  )
  
  
  
  
  
  
  def       __a       (   SCREAMING_SNAKE_CASE       ,   )      ->     list[Point]:
  
  
  
  
  
  
      '''simple docstring'''
      __UpperCAmelCase									=			[]
      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       __a       (   SCREAMING_SNAKE_CASE      )      ->     list[Point]:
  
  
  
  
  
  
      '''simple docstring'''
  
      if not hasattr(SCREAMING_SNAKE_CASE       ,   '''__iter__'''      ):
          __UpperCAmelCase									=			f'''Expecting an iterable object but got an non-iterable type {points}'''
          raise ValueError(SCREAMING_SNAKE_CASE      )
  
      if not points:
          __UpperCAmelCase									=			f'''Expecting a list of points but got {points}'''
          raise ValueError(SCREAMING_SNAKE_CASE      )
  
      return _construct_points(SCREAMING_SNAKE_CASE      )
  
  
  def       __a       (   SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE      )      ->     float:
  
  
  
  
  
  
      '''simple docstring'''
      __UpperCAmelCase									=			(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       (   SCREAMING_SNAKE_CASE      )      ->     list[Point]:
  
  
  
  
  
  
      '''simple docstring'''
      __UpperCAmelCase									=			sorted(_validate_input(SCREAMING_SNAKE_CASE      )      )
      __UpperCAmelCase									=			len(SCREAMING_SNAKE_CASE      )
      __UpperCAmelCase									=			set()
  
      for i in range(n - 1      ):
          for j in range(i + 1       ,   SCREAMING_SNAKE_CASE      ):
              __UpperCAmelCase									=			__UpperCAmelCase									=			False
              __UpperCAmelCase									=			True
              for k in range(SCREAMING_SNAKE_CASE      ):
                  if k != i and k != j:
                      __UpperCAmelCase									=			_det(points[i]       ,   points[j]       ,   points[k]      )
  
                      if det_k > 0:
                          __UpperCAmelCase									=			True
                      elif det_k < 0:
                          __UpperCAmelCase									=			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]:
                              __UpperCAmelCase									=			False
                              break
  
                  if points_left_of_ij and points_right_of_ij:
                      __UpperCAmelCase									=			False
                      break
  
              if ij_part_of_convex_hull:
                  convex_set.update([points[i], points[j]]      )
  
      return sorted(SCREAMING_SNAKE_CASE      )
  
  
  def       __a       (   SCREAMING_SNAKE_CASE      )      ->     list[Point]:
  
  
  
  
  
  
      '''simple docstring'''
      __UpperCAmelCase									=			sorted(_validate_input(SCREAMING_SNAKE_CASE      )      )
      __UpperCAmelCase									=			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
  
      __UpperCAmelCase									=			points[0]
      __UpperCAmelCase									=			points[n - 1]
  
      __UpperCAmelCase									=			{left_most_point, right_most_point}
      __UpperCAmelCase									=			[]
      __UpperCAmelCase									=			[]
  
      for i in range(1       ,   n - 1      ):
          __UpperCAmelCase									=			_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       __a       (   SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE      )      ->     None:
  
  
  
  
  
  
      '''simple docstring'''
      if points:
          __UpperCAmelCase									=			None
          __UpperCAmelCase									=			float('''-inf'''      )
          __UpperCAmelCase									=			[]
  
          for p in points:
              __UpperCAmelCase									=			_det(SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE      )
  
              if det > 0:
                  candidate_points.append(SCREAMING_SNAKE_CASE      )
  
                  if det > extreme_point_distance:
                      __UpperCAmelCase									=			det
                      __UpperCAmelCase									=			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       __a       (   SCREAMING_SNAKE_CASE      )      ->     list[Point]:
  
  
  
  
  
  
      '''simple docstring'''
      __UpperCAmelCase									=			sorted(_validate_input(SCREAMING_SNAKE_CASE      )      )
      __UpperCAmelCase									=			len(SCREAMING_SNAKE_CASE      )
  
      __UpperCAmelCase									=			points[:2]
      for i in range(2       ,   SCREAMING_SNAKE_CASE      ):
          __UpperCAmelCase									=			_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:
              __UpperCAmelCase									=			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       __a       (   )      ->     Any:
  
  
  
  
  
  
      '''simple docstring'''
      __UpperCAmelCase									=			[
          (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)]
      __UpperCAmelCase									=			convex_hull_bf(SCREAMING_SNAKE_CASE      )
  
      __UpperCAmelCase									=			convex_hull_recursive(SCREAMING_SNAKE_CASE      )
      assert results_bf == results_recursive
  
      __UpperCAmelCase									=			convex_hull_melkman(SCREAMING_SNAKE_CASE      )
      assert results_bf == results_melkman
  
      print(SCREAMING_SNAKE_CASE      )
  
  
  if __name__ == "__main__":
         main()
  
  
  
  
  
style_context: 
  
  import numpy as np
  
  
  def       __a       (   SCREAMING_SNAKE_CASE      )      ->     Tuple:
  
  
  
  
  
  
      '''simple docstring'''
      __UpperCAmelCase					,     __UpperCAmelCase									=			a.shape
      __UpperCAmelCase									=			min(SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE      )
      __UpperCAmelCase									=			np.eye(SCREAMING_SNAKE_CASE      )
      __UpperCAmelCase									=			a.copy()
  
      for k in range(t - 1      ):
          # select a column of modified matrix A':
          __UpperCAmelCase									=			r[k:, [k]]
          # construct first basis vector
          __UpperCAmelCase									=			np.zeros_like(SCREAMING_SNAKE_CASE      )
          __UpperCAmelCase									=			1.0
          # determine scaling factor
          __UpperCAmelCase									=			np.linalg.norm(SCREAMING_SNAKE_CASE      )
          # construct vector v for Householder reflection
          __UpperCAmelCase									=			x + np.sign(x[0]      ) * alpha * ea
          v /= np.linalg.norm(SCREAMING_SNAKE_CASE      )
  
          # construct the Householder matrix
          __UpperCAmelCase									=			np.eye(m - k      ) - 2.0 * v @ v.T
          # pad with ones and zeros as necessary
          __UpperCAmelCase									=			np.block([[np.eye(SCREAMING_SNAKE_CASE      ), np.zeros((k, m - k)      )], [np.zeros((m - k, k)      ), q_k]]      )
  
          __UpperCAmelCase									=			q @ q_k.T
          __UpperCAmelCase									=			q_k @ r
  
      return q, r
  
  
  if __name__ == "__main__":
         import doctest
  
         doctest.testmod()
  
  
  
  
  