'''simple docstring'''




from __future__ import annotations

from collections.abc import Iterable




class       __UpperCAmelCase							:





       '''simple docstring'''



       def __init__( self       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE					)						->	List[Any]:
           A_  ,A_      =  float(_SCREAMING_SNAKE_CASE					), float(_SCREAMING_SNAKE_CASE					)

       def __eq__( self       ,	_SCREAMING_SNAKE_CASE					)						->	Dict:
           return self.x == other.x and self.y == other.y

       def __ne__( self       ,	_SCREAMING_SNAKE_CASE					)						->	int:
           return not self == other

       def __gt__( self       ,	_SCREAMING_SNAKE_CASE					)						->	Optional[int]:
           if self.x > other.x:
               return True
           elif self.x == other.x:
               return self.y > other.y
           return False

       def __lt__( self       ,	_SCREAMING_SNAKE_CASE					)						->	List[Any]:
           return not self > other

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

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

       def __repr__( self					)						->	int:
           return F'''({self.x}, {self.y})'''

       def __hash__( self					)						->	Union[str, Any]:
           return hash(self.x					)





def 	_UpperCAmelCase       (				_UpperCamelCase       :      list[Point] | list[list[float]] | Iterable[list[float]],  )      -> list[Point]:
    A_      =  []
    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] | list[list[float]]  )      -> list[Point]:

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

    if not points:
        A_      =  F'''Expecting a list of points but got {points}'''
        raise ValueError(_UpperCamelCase  )

    return _construct_points(_UpperCamelCase  )





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

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

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

                if points_left_of_ij and points_right_of_ij:
                    A_      =  False
                    break

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

    return sorted(_UpperCamelCase  )





def 	_UpperCAmelCase       (				_UpperCamelCase       :      list[Point]  )      -> list[Point]:
    A_      =  sorted(_validate_input(_UpperCamelCase  )  )
    A_      =  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

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

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

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

        for p in points:
            A_      =  _det(_UpperCamelCase,  _UpperCamelCase,  _UpperCamelCase  )

            if det > 0:
                candidate_points.append(_UpperCamelCase  )

                if det > extreme_point_distance:
                    A_      =  det
                    A_      =  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]  )      -> list[Point]:
    A_      =  sorted(_validate_input(_UpperCamelCase  )  )
    A_      =  len(_UpperCamelCase  )

    A_      =  points[:2]
    for i in range(2,  _UpperCamelCase  ):
        A_      =  _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:
            A_      =  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       (				)      -> Tuple:
    A_      =  [
        (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)]
    A_      =  convex_hull_bf(_UpperCamelCase  )

    A_      =  convex_hull_recursive(_UpperCamelCase  )
    assert results_bf == results_recursive

    A_      =  convex_hull_melkman(_UpperCamelCase  )
    assert results_bf == results_melkman

    print(_UpperCamelCase  )


if __name__ == "__main__":
  main()







'''simple docstring'''




import json
import os
import tempfile

import datasets
from utils import generate_example_dataset, get_duration


__snake_case  : Dict		       =    500_000

__snake_case       ,       __snake_case  : List[str]		       =    os.path.split(__file__)
__snake_case  : Optional[Any]		       =    os.path.join(RESULTS_BASEPATH, 'results', RESULTS_FILENAME.replace('.py', '.json'))





@get_duration
def 	_UpperCAmelCase       (				_UpperCamelCase       :      datasets.Dataset  )      -> Union[str, Any]:
    A_      =  dataset.select(range(0,  len(_UpperCamelCase  ),  2  )  )





@get_duration
def 	_UpperCAmelCase       (				_UpperCamelCase       :      datasets.Dataset  )      -> str:
    A_      =  dataset.sort('''numbers'''  )





@get_duration
def 	_UpperCAmelCase       (				_UpperCamelCase       :      datasets.Dataset  )      -> str:
    A_      =  dataset.shuffle()





@get_duration
def 	_UpperCAmelCase       (				_UpperCamelCase       :      datasets.Dataset  )      -> Optional[Any]:
    A_      =  dataset.train_test_split(0.1  )





@get_duration
def 	_UpperCAmelCase       (				_UpperCamelCase       :      datasets.Dataset,  _UpperCamelCase       :      Optional[int]=10  )      -> Dict:
    for shard_id in range(_UpperCamelCase  ):
        A_      =  dataset.shard(_UpperCamelCase,  _UpperCamelCase  )





def 	_UpperCAmelCase       (				)      -> Any:
    A_      =  {'''num examples''': SPEED_TEST_N_EXAMPLES}
    A_      =  (select, sort, shuffle, train_test_split, shard)
    with tempfile.TemporaryDirectory() as tmp_dir:
        print('''generating dataset'''  )
        A_      =  datasets.Features({'''text''': datasets.Value('''string'''  ), '''numbers''': datasets.Value('''float32'''  )}  )
        A_      =  generate_example_dataset(
            os.path.join(_UpperCamelCase,  '''dataset.arrow'''  ),  _UpperCamelCase,  num_examples=_UpperCamelCase  )
        print('''Functions'''  )
        for func in functions:
            print(func.__name__  )
            A_      =  func(_UpperCamelCase  )

    with open(_UpperCamelCase,  '''wb'''  ) as f:
        f.write(json.dumps(_UpperCamelCase  ).encode('''utf-8'''  )  )


if __name__ == "__main__":  # useful to run the profiler
  benchmark_indices_mapping()






