"""simple docstring"""


from __future__ import annotations

from collections.abc import Iterable




class 					UpperCamelCase   :







       def __init__(					self,				lowerCAmelCase__,				lowerCAmelCase__) -> Optional[int]:
            snake_case_			,      snake_case_   			=   float(lowerCAmelCase__), float(lowerCAmelCase__)







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







       def __ne__(					self,				lowerCAmelCase__) -> Any:
            return not self == other







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







       def __lt__(					self,				lowerCAmelCase__) -> Tuple:
            return not self > other







       def __ge__(					self,				lowerCAmelCase__) -> List[str]:
            if self.x > other.x:
                 return True
            elif self.x == other.x:
                 return self.y >= other.y
            return False







       def __le__(					self,				lowerCAmelCase__) -> Any:
            if self.x < other.x:
                 return True
            elif self.x == other.x:
                 return self.y <= other.y
            return False







       def __repr__(					self) -> List[Any]:
            return f'({self.x}, {self.y})'







       def __hash__(					self) -> Tuple:
            return hash(self.x)







def    UpperCAmelCase       (						UpperCAmelCase		,   )							-> list[Point]:
     snake_case_   			=   []
     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   )							-> list[Point]:

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

     if not points:
          snake_case_   			=   f'Expecting a list of points but got {points}'
          raise ValueError(UpperCAmelCase   )

     return _construct_points(UpperCAmelCase   )







def    UpperCAmelCase       (						UpperCAmelCase		,   UpperCAmelCase		,   UpperCAmelCase   )							-> float:
     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    UpperCAmelCase       (						UpperCAmelCase   )							-> list[Point]:
     snake_case_   			=   sorted(_validate_input(UpperCAmelCase   )   )
     snake_case_   			=   len(UpperCAmelCase   )
     snake_case_   			=   set()

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

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

                    if points_left_of_ij and points_right_of_ij:
                         snake_case_   			=   False
                         break

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

     return sorted(UpperCAmelCase   )







def    UpperCAmelCase       (						UpperCAmelCase   )							-> list[Point]:
     snake_case_   			=   sorted(_validate_input(UpperCAmelCase   )   )
     snake_case_   			=   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

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

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

     for i in range(1		,   n - 1   ):
          snake_case_   			=   _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   )							-> None:
     if points:
          snake_case_   			=   None
          snake_case_   			=   float('-inf'   )
          snake_case_   			=   []

          for p in points:
               snake_case_   			=   _det(UpperCAmelCase		,   UpperCAmelCase		,   UpperCAmelCase   )

               if det > 0:
                    candidate_points.append(UpperCAmelCase   )

                    if det > extreme_point_distance:
                         snake_case_   			=   det
                         snake_case_   			=   p

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







def    UpperCAmelCase       (						UpperCAmelCase   )							-> list[Point]:
     snake_case_   			=   sorted(_validate_input(UpperCAmelCase   )   )
     snake_case_   			=   len(UpperCAmelCase   )

     snake_case_   			=   points[:2]
     for i in range(2		,   UpperCAmelCase   ):
          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:
               snake_case_   			=   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       (						)							-> Optional[Any]:
     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)]
     snake_case_   			=   convex_hull_bf(UpperCAmelCase   )

     snake_case_   			=   convex_hull_recursive(UpperCAmelCase   )
     assert results_bf == results_recursive

     snake_case_   			=   convex_hull_melkman(UpperCAmelCase   )
     assert results_bf == results_melkman

     print(UpperCAmelCase   )


if __name__ == "__main__":
    main()


"""simple docstring"""


import random
import sys

__UpperCamelCase										=     '''ABCDEFGHIJKLMNOPQRSTUVWXYZ'''







def    UpperCAmelCase       (						)							-> None:
     snake_case_   			=   input('Enter message: '   )
     snake_case_   			=   'LFWOAYUISVKMNXPBDCRJTQEGHZ'
     snake_case_   			=   input('Encrypt/Decrypt [e/d]: '   )

     check_valid_key(UpperCAmelCase   )

     if resp.lower().startswith('e'   ):
          snake_case_   			=   'encrypt'
          snake_case_   			=   encrypt_message(UpperCAmelCase		,   UpperCAmelCase   )
     elif resp.lower().startswith('d'   ):
          snake_case_   			=   'decrypt'
          snake_case_   			=   decrypt_message(UpperCAmelCase		,   UpperCAmelCase   )

     print(f'\n{mode.title()}ion: \n{translated}'   )







def    UpperCAmelCase       (						UpperCAmelCase   )							-> None:
     snake_case_   			=   list(UpperCAmelCase   )
     snake_case_   			=   list(UpperCAmelCase   )
     key_list.sort()
     letters_list.sort()

     if key_list != letters_list:
          sys.exit('Error in the key or symbol set.'   )







def    UpperCAmelCase       (						UpperCAmelCase		,   UpperCAmelCase   )							-> str:
     return translate_message(UpperCAmelCase		,   UpperCAmelCase		,   'encrypt'   )







def    UpperCAmelCase       (						UpperCAmelCase		,   UpperCAmelCase   )							-> str:
     return translate_message(UpperCAmelCase		,   UpperCAmelCase		,   'decrypt'   )







def    UpperCAmelCase       (						UpperCAmelCase		,   UpperCAmelCase		,   UpperCAmelCase   )							-> str:
     snake_case_   			=   ''
     snake_case_   			=   LETTERS
     snake_case_   			=   key

     if mode == "decrypt":
          snake_case_			,      snake_case_   			=   chars_b, chars_a

     for symbol in message:
          if symbol.upper() in chars_a:
               snake_case_   			=   chars_a.find(symbol.upper()   )
               if symbol.isupper():
                    translated += chars_b[sym_index].upper()
               else:
                    translated += chars_b[sym_index].lower()
          else:
               translated += symbol

     return translated







def    UpperCAmelCase       (						)							-> str:
     snake_case_   			=   list(UpperCAmelCase   )
     random.shuffle(UpperCAmelCase   )
     return "".join(UpperCAmelCase   )


if __name__ == "__main__":
    main()

