


'''simple docstring'''

from __future__ import annotations

from collections.abc import Iterable


class    a__					:







				"""simple docstring"""



				def __init__(self							,      __lowercase							,      __lowercase		):
										__lowerCAmelCase											=					float(_a		), float(_a		)




				def __eq__(self							,      __lowercase		):
										return self.x == other.x and self.y == other.y




				def __ne__(self							,      __lowercase		):
										return not self == other




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




				def __lt__(self							,      __lowercase		):
										return not self > other




				def __ge__(self							,      __lowercase		):
										if self.x > other.x:
																return True
										elif self.x == other.x:
																return self.y >= other.y
										return False




				def __le__(self							,      __lowercase		):
										if self.x < other.x:
																return True
										elif self.x == other.x:
																return self.y <= other.y
										return False




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




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

def 				__magic_name__(    lowerCamelCase,					):
						__lowerCAmelCase											=					[]
						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 				__magic_name__(    lowerCamelCase):

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

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

						return _construct_points(SCREAMING_SNAKE_CASE_)

def 				__magic_name__(    lowerCamelCase,					lowerCamelCase,					lowerCamelCase):
						__lowerCAmelCase											=					(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 				__magic_name__(    lowerCamelCase):
						__lowerCAmelCase											=					sorted(_validate_input(SCREAMING_SNAKE_CASE_))
						__lowerCAmelCase											=					len(SCREAMING_SNAKE_CASE_)
						__lowerCAmelCase											=					set()

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

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

																								if points_left_of_ij and points_right_of_ij:
																														__lowerCAmelCase											=					False
																														break

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

						return sorted(SCREAMING_SNAKE_CASE_)

def 				__magic_name__(    lowerCamelCase):
						__lowerCAmelCase											=					sorted(_validate_input(SCREAMING_SNAKE_CASE_))
						__lowerCAmelCase											=					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

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

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

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

												for p in points:
																		__lowerCAmelCase											=					_det(SCREAMING_SNAKE_CASE_,					SCREAMING_SNAKE_CASE_,					SCREAMING_SNAKE_CASE_)

																		if det > 0:
																								candidate_points.append(SCREAMING_SNAKE_CASE_)

																								if det > extreme_point_distance:
																														__lowerCAmelCase											=					det
																														__lowerCAmelCase											=					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 				__magic_name__(    lowerCamelCase):
						__lowerCAmelCase											=					sorted(_validate_input(SCREAMING_SNAKE_CASE_))
						__lowerCAmelCase											=					len(SCREAMING_SNAKE_CASE_)

						__lowerCAmelCase											=					points[:2]
						for i in range(2,					SCREAMING_SNAKE_CASE_):
												__lowerCAmelCase											=					_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:
																		__lowerCAmelCase											=					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 				__magic_name__(    ):
						__lowerCAmelCase											=					[
						    (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)]
						__lowerCAmelCase											=					convex_hull_bf(SCREAMING_SNAKE_CASE_)

						__lowerCAmelCase											=					convex_hull_recursive(SCREAMING_SNAKE_CASE_)
						assert results_bf == results_recursive

						__lowerCAmelCase											=					convex_hull_melkman(SCREAMING_SNAKE_CASE_)
						assert results_bf == results_melkman

						print(SCREAMING_SNAKE_CASE_)


if __name__ == "__main__":
	main()


'''simple docstring'''




import os

from packaging import version

from .. import __version__
from .accelerate_utils import apply_forward_hook
from .constants import (
    CONFIG_NAME,
    DEPRECATED_REVISION_ARGS,
    DIFFUSERS_CACHE,
    DIFFUSERS_DYNAMIC_MODULE_NAME,
    FLAX_WEIGHTS_NAME,
    HF_MODULES_CACHE,
    HUGGINGFACE_CO_RESOLVE_ENDPOINT,
    ONNX_EXTERNAL_WEIGHTS_NAME,
    ONNX_WEIGHTS_NAME,
    SAFETENSORS_WEIGHTS_NAME,
    TEXT_ENCODER_ATTN_MODULE,
    WEIGHTS_NAME,
)
from .deprecation_utils import deprecate
from .doc_utils import replace_example_docstring
from .dynamic_modules_utils import get_class_from_dynamic_module
from .hub_utils import (
    HF_HUB_OFFLINE,
    _add_variant,
    _get_model_file,
    extract_commit_hash,
    http_user_agent,
)
from .import_utils import (
    BACKENDS_MAPPING,
    ENV_VARS_TRUE_AND_AUTO_VALUES,
    ENV_VARS_TRUE_VALUES,
    USE_JAX,
    USE_TF,
    USE_TORCH,
    DummyObject,
    OptionalDependencyNotAvailable,
    is_accelerate_available,
    is_accelerate_version,
    is_bsa_available,
    is_flax_available,
    is_ftfy_available,
    is_inflect_available,
    is_invisible_watermark_available,
    is_k_diffusion_available,
    is_k_diffusion_version,
    is_librosa_available,
    is_note_seq_available,
    is_omegaconf_available,
    is_onnx_available,
    is_safetensors_available,
    is_scipy_available,
    is_tensorboard_available,
    is_tf_available,
    is_torch_available,
    is_torch_version,
    is_torchsde_available,
    is_transformers_available,
    is_transformers_version,
    is_unidecode_available,
    is_wandb_available,
    is_xformers_available,
    requires_backends,
)
from .logging import get_logger
from .outputs import BaseOutput
from .pil_utils import PIL_INTERPOLATION, numpy_to_pil, pt_to_pil
from .torch_utils import is_compiled_module, randn_tensor


if is_torch_available():
 from .testing_utils import (
     floats_tensor,
     load_hf_numpy,
     load_image,
     load_numpy,
     load_pt,
     nightly,
     parse_flag_from_env,
     print_tensor_test,
     require_torch_a,
     require_torch_gpu,
     skip_mps,
     slow,
     torch_all_close,
     torch_device,
 )
 from .torch_utils import maybe_allow_in_graph

from .testing_utils import export_to_gif, export_to_video


_A										= get_logger(__name__)

def _UpperCamelCase (							SCREAMING_SNAKE_CASE_				):
     if version.parse(SCREAMING_SNAKE_CASE_				) < version.parse(SCREAMING_SNAKE_CASE_				):
          if "dev" in min_version:
               lowercase_       :							Tuple  					=       (
                   'This example requires a source install from HuggingFace diffusers (see '
                   '`https://huggingface.co/docs/diffusers/installation#install-from-source`),'
               )
          else:
               lowercase_       :							List[Any]  					=       f'''This example requires a minimum version of {min_version},'''
          error_message += f''' but the version found is {__version__}.\n'''
          raise ImportError(SCREAMING_SNAKE_CASE_				)




