

from __future__ import annotations

from collections.abc import Iterable





class       __UpperCAmelCase  :



   def __init__(							self							:  Any,	__A							:  List[str],	__A							:  str		):
     UpperCAmelCase :							Optional[Any]								=				float(__A		), float(__A		)



   def __eq__(							self							:  Union[str, Any],	__A							:  List[Any]		):
     return self.x == other.x and self.y == other.y



   def __ne__(							self							:  str,	__A							:  Optional[Any]		):
     return not self == other



   def __gt__(							self							:  Any,	__A							:  Any		):
     if self.x > other.x:
       return True
     elif self.x == other.x:
       return self.y > other.y
     return False



   def __lt__(							self							:  str,	__A							:  Dict		):
     return not self > other



   def __ge__(							self							:  Optional[int],	__A							:  Dict		):
     if self.x > other.x:
       return True
     elif self.x == other.x:
       return self.y >= other.y
     return False



   def __le__(							self							:  Optional[Any],	__A							:  int		):
     if self.x < other.x:
       return True
     elif self.x == other.x:
       return self.y <= other.y
     return False



   def __repr__(							self							:  Any		):
     return F'''({self.x}, {self.y})'''





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






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

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

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

  return _construct_points(UpperCAmelCase    )

def     a__  (	UpperCAmelCase							:    Point       ,				UpperCAmelCase							:    Point       ,				UpperCAmelCase							:    Point    )						->		float:
  UpperCAmelCase :							Tuple								=				(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__  (	UpperCAmelCase							:    list[Point]    )						->		list[Point]:
  UpperCAmelCase :							Dict								=				sorted(_validate_input(UpperCAmelCase    )    )
  UpperCAmelCase :							str								=				len(UpperCAmelCase    )
  UpperCAmelCase :							int								=				set()

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

          if det_k > 0:
            UpperCAmelCase :							Tuple								=				True
          elif det_k < 0:
            UpperCAmelCase :							Tuple								=				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 :							Dict								=				False
              break

        if points_left_of_ij and points_right_of_ij:
          UpperCAmelCase :							str								=				False
          break

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

  return sorted(UpperCAmelCase    )

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

  UpperCAmelCase :							List[Any]								=				points[0]
  UpperCAmelCase :							str								=				points[n - 1]

  UpperCAmelCase :							str								=				{left_most_point, right_most_point}
  UpperCAmelCase :							Optional[Any]								=				[]
  UpperCAmelCase :							Optional[Any]								=				[]

  for i in range(1       ,				n - 1    ):
    UpperCAmelCase :							Dict								=				_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     a__  (	UpperCAmelCase							:    list[Point]       ,				UpperCAmelCase							:    Point       ,				UpperCAmelCase							:    Point       ,				UpperCAmelCase							:    set[Point]    )						->		None:
  if points:
    UpperCAmelCase :							Dict								=				None
    UpperCAmelCase :							Optional[int]								=				float('''-inf'''    )
    UpperCAmelCase :							Any								=				[]

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

      if det > 0:
        candidate_points.append(UpperCAmelCase    )

        if det > extreme_point_distance:
          UpperCAmelCase :							Any								=				det
          UpperCAmelCase :							Dict								=				p

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

def     a__  (	UpperCAmelCase							:    list[Point]    )						->		list[Point]:
  UpperCAmelCase :							str								=				sorted(_validate_input(UpperCAmelCase    )    )
  UpperCAmelCase :							List[Any]								=				len(UpperCAmelCase    )

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

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

  UpperCAmelCase :							List[Any]								=				convex_hull_melkman(UpperCAmelCase    )
  assert results_bf == results_melkman

  print(UpperCAmelCase    )


if __name__ == "__main__":
     main()








import csv
import os

import pytest

from datasets import Dataset, DatasetDict, Features, NamedSplit, Value
from datasets.io.csv import CsvDatasetReader, CsvDatasetWriter

from ..utils import assert_arrow_memory_doesnt_increase, assert_arrow_memory_increases

def     a__  (	UpperCAmelCase							:    int       ,				UpperCAmelCase							:    int    )						->		List[str]:
  assert isinstance(UpperCAmelCase       ,				UpperCAmelCase    )
  assert dataset.num_rows == 4
  assert dataset.num_columns == 3
  assert dataset.column_names == ["col_1", "col_2", "col_3"]
  for feature, expected_dtype in expected_features.items():
    assert dataset.features[feature].dtype == expected_dtype

@pytest.mark.parametrize('''keep_in_memory'''       ,				[False, True]    )
def     a__  (	UpperCAmelCase							:    Any       ,				UpperCAmelCase							:    List[Any]       ,				UpperCAmelCase							:    Optional[Any]    )						->		Optional[int]:
  UpperCAmelCase :							Optional[int]								=				tmp_path / '''cache'''
  UpperCAmelCase :							str								=				{'''col_1''': '''int64''', '''col_2''': '''int64''', '''col_3''': '''float64'''}
  with assert_arrow_memory_increases() if keep_in_memory else assert_arrow_memory_doesnt_increase():
    UpperCAmelCase :							Union[str, Any]								=				CsvDatasetReader(UpperCAmelCase       ,				cache_dir=UpperCAmelCase       ,				keep_in_memory=UpperCAmelCase    ).read()
  _check_csv_dataset(UpperCAmelCase       ,				UpperCAmelCase    )

@pytest.mark.parametrize(
    '''features'''       ,				[
        None,
        {'''col_1''': '''string''', '''col_2''': '''int64''', '''col_3''': '''float64'''},
        {'''col_1''': '''string''', '''col_2''': '''string''', '''col_3''': '''string'''},
        {'''col_1''': '''int32''', '''col_2''': '''int32''', '''col_3''': '''int32'''},
        {'''col_1''': '''float32''', '''col_2''': '''float32''', '''col_3''': '''float32'''},
    ]       ,				)
def     a__  (	UpperCAmelCase							:    Optional[int]       ,				UpperCAmelCase							:    int       ,				UpperCAmelCase							:    int    )						->		Optional[Any]:
  UpperCAmelCase :							List[str]								=				tmp_path / '''cache'''
  # CSV file loses col_1 string dtype information: default now is "int64" instead of "string"
  UpperCAmelCase :							Optional[Any]								=				{'''col_1''': '''int64''', '''col_2''': '''int64''', '''col_3''': '''float64'''}
  UpperCAmelCase :							List[Any]								=				features.copy() if features else default_expected_features
  UpperCAmelCase :							List[Any]								=				(
      Features({feature: Value(UpperCAmelCase    ) for feature, dtype in features.items()}    ) if features is not None else None
  )
  UpperCAmelCase :							Any								=				CsvDatasetReader(UpperCAmelCase       ,				features=UpperCAmelCase       ,				cache_dir=UpperCAmelCase    ).read()
  _check_csv_dataset(UpperCAmelCase       ,				UpperCAmelCase    )

@pytest.mark.parametrize('''split'''       ,				[None, NamedSplit('''train'''    ), '''train''', '''test''']    )
def     a__  (	UpperCAmelCase							:    Union[str, Any]       ,				UpperCAmelCase							:    Tuple       ,				UpperCAmelCase							:    str    )						->		Any:
  UpperCAmelCase :							List[str]								=				tmp_path / '''cache'''
  UpperCAmelCase :							Any								=				{'''col_1''': '''int64''', '''col_2''': '''int64''', '''col_3''': '''float64'''}
  UpperCAmelCase :							int								=				CsvDatasetReader(UpperCAmelCase       ,				cache_dir=UpperCAmelCase       ,				split=UpperCAmelCase    ).read()
  _check_csv_dataset(UpperCAmelCase       ,				UpperCAmelCase    )
  assert dataset.split == split if split else "train"

@pytest.mark.parametrize('''path_type'''       ,				[str, list]    )
def     a__  (	UpperCAmelCase							:    int       ,				UpperCAmelCase							:    List[str]       ,				UpperCAmelCase							:    Any    )						->		str:
  if issubclass(UpperCAmelCase       ,				UpperCAmelCase    ):
    UpperCAmelCase :							Tuple								=				csv_path
  elif issubclass(UpperCAmelCase       ,				UpperCAmelCase    ):
    UpperCAmelCase :							List[str]								=				[csv_path]
  UpperCAmelCase :							Tuple								=				tmp_path / '''cache'''
  UpperCAmelCase :							str								=				{'''col_1''': '''int64''', '''col_2''': '''int64''', '''col_3''': '''float64'''}
  UpperCAmelCase :							Tuple								=				CsvDatasetReader(UpperCAmelCase       ,				cache_dir=UpperCAmelCase    ).read()
  _check_csv_dataset(UpperCAmelCase       ,				UpperCAmelCase    )

def     a__  (	UpperCAmelCase							:    str       ,				UpperCAmelCase							:    Any       ,				UpperCAmelCase							:    int=("train",)    )						->		Optional[int]:
  assert isinstance(UpperCAmelCase       ,				UpperCAmelCase    )
  for split in splits:
    UpperCAmelCase :							Optional[Any]								=				dataset_dict[split]
    assert dataset.num_rows == 4
    assert dataset.num_columns == 3
    assert dataset.column_names == ["col_1", "col_2", "col_3"]
    for feature, expected_dtype in expected_features.items():
      assert dataset.features[feature].dtype == expected_dtype

@pytest.mark.parametrize('''keep_in_memory'''       ,				[False, True]    )
def     a__  (	UpperCAmelCase							:    Tuple       ,				UpperCAmelCase							:    List[Any]       ,				UpperCAmelCase							:    Tuple    )						->		Tuple:
  UpperCAmelCase :							Any								=				tmp_path / '''cache'''
  UpperCAmelCase :							Dict								=				{'''col_1''': '''int64''', '''col_2''': '''int64''', '''col_3''': '''float64'''}
  with assert_arrow_memory_increases() if keep_in_memory else assert_arrow_memory_doesnt_increase():
    UpperCAmelCase :							str								=				CsvDatasetReader({'''train''': csv_path}       ,				cache_dir=UpperCAmelCase       ,				keep_in_memory=UpperCAmelCase    ).read()
  _check_csv_datasetdict(UpperCAmelCase       ,				UpperCAmelCase    )

@pytest.mark.parametrize(
    '''features'''       ,				[
        None,
        {'''col_1''': '''string''', '''col_2''': '''int64''', '''col_3''': '''float64'''},
        {'''col_1''': '''string''', '''col_2''': '''string''', '''col_3''': '''string'''},
        {'''col_1''': '''int32''', '''col_2''': '''int32''', '''col_3''': '''int32'''},
        {'''col_1''': '''float32''', '''col_2''': '''float32''', '''col_3''': '''float32'''},
    ]       ,				)
def     a__  (	UpperCAmelCase							:    int       ,				UpperCAmelCase							:    Tuple       ,				UpperCAmelCase							:    Any    )						->		Optional[int]:
  UpperCAmelCase :							Tuple								=				tmp_path / '''cache'''
  # CSV file loses col_1 string dtype information: default now is "int64" instead of "string"
  UpperCAmelCase :							List[str]								=				{'''col_1''': '''int64''', '''col_2''': '''int64''', '''col_3''': '''float64'''}
  UpperCAmelCase :							Union[str, Any]								=				features.copy() if features else default_expected_features
  UpperCAmelCase :							List[str]								=				(
      Features({feature: Value(UpperCAmelCase    ) for feature, dtype in features.items()}    ) if features is not None else None
  )
  UpperCAmelCase :							List[Any]								=				CsvDatasetReader({'''train''': csv_path}       ,				features=UpperCAmelCase       ,				cache_dir=UpperCAmelCase    ).read()
  _check_csv_datasetdict(UpperCAmelCase       ,				UpperCAmelCase    )

@pytest.mark.parametrize('''split'''       ,				[None, NamedSplit('''train'''    ), '''train''', '''test''']    )
def     a__  (	UpperCAmelCase							:    Union[str, Any]       ,				UpperCAmelCase							:    List[Any]       ,				UpperCAmelCase							:    Optional[Any]    )						->		Dict:
  if split:
    UpperCAmelCase :							Union[str, Any]								=				{split: csv_path}
  else:
    UpperCAmelCase :							List[str]								=				{'''train''': csv_path, '''test''': csv_path}
  UpperCAmelCase :							str								=				tmp_path / '''cache'''
  UpperCAmelCase :							Tuple								=				{'''col_1''': '''int64''', '''col_2''': '''int64''', '''col_3''': '''float64'''}
  UpperCAmelCase :							str								=				CsvDatasetReader(UpperCAmelCase       ,				cache_dir=UpperCAmelCase    ).read()
  _check_csv_datasetdict(UpperCAmelCase       ,				UpperCAmelCase       ,				splits=list(path.keys()    )    )
  assert all(dataset[split].split == split for split in path.keys()    )

def     a__  (	UpperCAmelCase							:    Optional[Any]    )						->		int:
  with open(UpperCAmelCase       ,				encoding='''utf-8'''    ) as csvfile:
    yield from csv.reader(UpperCAmelCase    )

def     a__  (	UpperCAmelCase							:    List[str]       ,				UpperCAmelCase							:    Union[str, Any]    )						->		Union[str, Any]:
  UpperCAmelCase :							int								=				tmp_path / '''cache'''
  UpperCAmelCase :							int								=				os.path.join(UpperCAmelCase       ,				'''tmp.csv'''    )
  UpperCAmelCase :							List[str]								=				CsvDatasetReader({'''train''': csv_path}       ,				cache_dir=UpperCAmelCase    ).read()
  CsvDatasetWriter(dataset['''train''']       ,				UpperCAmelCase       ,				num_proc=1    ).write()

  UpperCAmelCase :							List[Any]								=				iter_csv_file(UpperCAmelCase    )
  UpperCAmelCase :							int								=				iter_csv_file(UpperCAmelCase    )

  for rowa, rowa in zip(UpperCAmelCase       ,				UpperCAmelCase    ):
    assert rowa == rowa

def     a__  (	UpperCAmelCase							:    Any       ,				UpperCAmelCase							:    Dict    )						->		Any:
  UpperCAmelCase :							List[Any]								=				tmp_path / '''cache'''
  UpperCAmelCase :							Tuple								=				os.path.join(UpperCAmelCase       ,				'''tmp.csv'''    )
  UpperCAmelCase :							List[str]								=				CsvDatasetReader({'''train''': csv_path}       ,				cache_dir=UpperCAmelCase    ).read()
  CsvDatasetWriter(dataset['''train''']       ,				UpperCAmelCase       ,				num_proc=2    ).write()

  UpperCAmelCase :							List[Any]								=				iter_csv_file(UpperCAmelCase    )
  UpperCAmelCase :							Union[str, Any]								=				iter_csv_file(UpperCAmelCase    )

  for rowa, rowa in zip(UpperCAmelCase       ,				UpperCAmelCase    ):
    assert rowa == rowa






def     a__  (	UpperCAmelCase							:    List[Any]       ,				UpperCAmelCase							:    Optional[int]    )						->		Optional[Any]:
  UpperCAmelCase :							Dict								=				tmp_path / '''cache'''
  UpperCAmelCase :							List[Any]								=				os.path.join(UpperCAmelCase       ,				'''tmp.csv'''    )
  UpperCAmelCase :							List[Any]								=				CsvDatasetReader({'''train''': csv_path}       ,				cache_dir=UpperCAmelCase    ).read()
  with pytest.raises(UpperCAmelCase    ):
    CsvDatasetWriter(dataset['''train''']       ,				UpperCAmelCase       ,				num_proc=0    )





