

import inspect
from typing import List, Optional, Union

import torch
from torch import nn
from torch.nn import functional as F
from torchvision import transforms
from transformers import CLIPImageProcessor, CLIPModel, CLIPTextModel, CLIPTokenizer

from diffusers import (
    AutoencoderKL,
    DDIMScheduler,
    DiffusionPipeline,
    DPMSolverMultistepScheduler,
    LMSDiscreteScheduler,
    PNDMScheduler,
    UNetaDConditionModel,
)
from diffusers.pipelines.stable_diffusion.pipeline_stable_diffusion import StableDiffusionPipelineOutput

class  a     (		nn.Module ):


						def __init__(				self  ,    A_  ,    A_=1.0		):







										'''simple docstring'''


										super().__init__()

										_UpperCAmelCase				:						str       						=			cut_size
										_UpperCAmelCase				:						Tuple       						=			cut_power





						def 				_UpperCAmelCase (				self  ,    A_  ,    A_		):







										'''simple docstring'''


										_UpperCAmelCase						,							_UpperCAmelCase				:						List[str]       						=			pixel_values.shape[2:4]
										_UpperCAmelCase				:						Dict       						=			min(A_  ,    A_		)
										_UpperCAmelCase				:						Any       						=			min(A_  ,    A_  ,    self.cut_size		)
										_UpperCAmelCase				:						List[Any]       						=			[]
										for _ in range(A_		):
														_UpperCAmelCase				:						Union[str, Any]       						=			int(torch.rand([]		) ** self.cut_power * (max_size - min_size) + min_size		)
														_UpperCAmelCase				:						int       						=			torch.randint(0  ,    sideX - size + 1  ,    ()		)
														_UpperCAmelCase				:						Dict       						=			torch.randint(0  ,    sideY - size + 1  ,    ()		)
														_UpperCAmelCase				:						Union[str, Any]       						=			pixel_values[:, :, offsety : offsety + size, offsetx : offsetx + size]
														cutouts.append(F.adaptive_avg_poolad(A_  ,    self.cut_size		)		)
										return torch.cat(A_		)







def 							__SCREAMING_SNAKE_CASE							( lowerCAmelCase:     Union[str, Any]     ,					lowerCAmelCase:     Tuple       )      ->				str:
				_UpperCAmelCase				:						Union[str, Any]       						=			F.normalize(lowerCAmelCase     ,					dim=-1       )
				_UpperCAmelCase				:						Tuple       						=			F.normalize(lowerCAmelCase     ,					dim=-1       )
				return (x - y).norm(dim=-1       ).div(2       ).arcsin().pow(2       ).mul(2       )

def 							__SCREAMING_SNAKE_CASE							( lowerCAmelCase:     Optional[Any]     ,					lowerCAmelCase:     Optional[Any]       )      ->				Optional[Any]:
				for param in model.parameters():
								_UpperCAmelCase				:						Any       						=			value





class  a     (		UpperCAmelCase ):


						def __init__(				self  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    ):







										'''simple docstring'''


										super().__init__()
										self.register_modules(
										    vae=A_  ,    text_encoder=A_  ,    clip_model=A_  ,    tokenizer=A_  ,    unet=A_  ,    scheduler=A_  ,    feature_extractor=A_  ,    )

										_UpperCAmelCase				:						Tuple       						=			transforms.Normalize(mean=feature_extractor.image_mean  ,    std=feature_extractor.image_std		)
										_UpperCAmelCase				:						Optional[int]       						=			(
										    feature_extractor.size
										    if isinstance(feature_extractor.size  ,    A_		)
										    else feature_extractor.size["shortest_edge"]
										)
										_UpperCAmelCase				:						List[Any]       						=			MakeCutouts(self.cut_out_size		)

										set_requires_grad(self.text_encoder  ,    A_		)
										set_requires_grad(self.clip_model  ,    A_		)


						def 				_UpperCAmelCase (				self  ,    A_ = "auto"		):







										'''simple docstring'''


										if slice_size == "auto":
														# half the attention head size is usually a good trade-off between
														# speed and memory
														_UpperCAmelCase				:						Any       						=			self.unet.config.attention_head_dim // 2
										self.unet.set_attention_slice(A_		)


						def 				_UpperCAmelCase (				self		):







										'''simple docstring'''


										self.enable_attention_slicing(A_		)


						def 				_UpperCAmelCase (				self		):







										'''simple docstring'''


										set_requires_grad(self.vae  ,    A_		)


						def 				_UpperCAmelCase (				self		):







										'''simple docstring'''


										set_requires_grad(self.vae  ,    A_		)


						def 				_UpperCAmelCase (				self		):







										'''simple docstring'''


										set_requires_grad(self.unet  ,    A_		)


						def 				_UpperCAmelCase (				self		):







										'''simple docstring'''


										set_requires_grad(self.unet  ,    A_		)


						@torch.enable_grad()
						def 				_UpperCAmelCase (				self  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_=True  ,    ):







										'''simple docstring'''


										_UpperCAmelCase				:						List[Any]       						=			latents.detach().requires_grad_()

										_UpperCAmelCase				:						Union[str, Any]       						=			self.scheduler.scale_model_input(A_  ,    A_		)

										# predict the noise residual
										_UpperCAmelCase				:						List[Any]       						=			self.unet(A_  ,    A_  ,    encoder_hidden_states=A_		).sample

										if isinstance(self.scheduler  ,    (PNDMScheduler, DDIMScheduler, DPMSolverMultistepScheduler)		):
														_UpperCAmelCase				:						Dict       						=			self.scheduler.alphas_cumprod[timestep]
														_UpperCAmelCase				:						List[str]       						=			1 - alpha_prod_t
														# compute predicted original sample from predicted noise also called
														# "predicted x_0" of formula (12) from https://arxiv.org/pdf/2010.02502.pdf
														_UpperCAmelCase				:						int       						=			(latents - beta_prod_t ** 0.5 * noise_pred) / alpha_prod_t ** 0.5

														_UpperCAmelCase				:						List[Any]       						=			torch.sqrt(A_		)
														_UpperCAmelCase				:						Optional[int]       						=			pred_original_sample * (fac) + latents * (1 - fac)
										elif isinstance(self.scheduler  ,    A_		):
														_UpperCAmelCase				:						str       						=			self.scheduler.sigmas[index]
														_UpperCAmelCase				:						List[Any]       						=			latents - sigma * noise_pred
										else:
														raise ValueError(f'scheduler type {type(self.scheduler		)} not supported'		)

										_UpperCAmelCase				:						Optional[int]       						=			1 / self.vae.config.scaling_factor * sample
										_UpperCAmelCase				:						int       						=			self.vae.decode(A_		).sample
										_UpperCAmelCase				:						Union[str, Any]       						=			(image / 2 + 0.5).clamp(0  ,    1		)

										if use_cutouts:
														_UpperCAmelCase				:						Tuple       						=			self.make_cutouts(A_  ,    A_		)
										else:
														_UpperCAmelCase				:						Tuple       						=			transforms.Resize(self.cut_out_size		)(A_		)
										_UpperCAmelCase				:						str       						=			self.normalize(A_		).to(latents.dtype		)

										_UpperCAmelCase				:						Union[str, Any]       						=			self.clip_model.get_image_features(A_		)
										_UpperCAmelCase				:						Dict       						=			image_embeddings_clip / image_embeddings_clip.norm(p=2  ,    dim=-1  ,    keepdim=A_		)

										if use_cutouts:
														_UpperCAmelCase				:						Dict       						=			spherical_dist_loss(A_  ,    A_		)
														_UpperCAmelCase				:						Optional[int]       						=			dists.view([num_cutouts, sample.shape[0], -1]		)
														_UpperCAmelCase				:						Union[str, Any]       						=			dists.sum(2		).mean(0		).sum() * clip_guidance_scale
										else:
														_UpperCAmelCase				:						Any       						=			spherical_dist_loss(A_  ,    A_		).mean() * clip_guidance_scale

										_UpperCAmelCase				:						List[str]       						=			-torch.autograd.grad(A_  ,    A_		)[0]

										if isinstance(self.scheduler  ,    A_		):
														_UpperCAmelCase				:						Dict       						=			latents.detach() + grads * (sigma**2)
														_UpperCAmelCase				:						List[str]       						=			noise_pred_original
										else:
														_UpperCAmelCase				:						Any       						=			noise_pred_original - torch.sqrt(A_		) * grads
										return noise_pred, latents





						@torch.no_grad()
						def __call__(				self  ,    A_  ,    A_ = 512  ,    A_ = 512  ,    A_ = 50  ,    A_ = 7.5  ,    A_ = 1  ,    A_ = 0.0  ,    A_ = 100  ,    A_ = None  ,    A_ = 4  ,    A_ = True  ,    A_ = None  ,    A_ = None  ,    A_ = "pil"  ,    A_ = True  ,    ):







										'''simple docstring'''


										if isinstance(A_  ,    A_		):
														_UpperCAmelCase				:						List[str]       						=			1
										elif isinstance(A_  ,    A_		):
														_UpperCAmelCase				:						int       						=			len(A_		)
										else:
														raise ValueError(f'`prompt` has to be of type `str` or `list` but is {type(A_		)}'		)

										if height % 8 != 0 or width % 8 != 0:
														raise ValueError(f'`height` and `width` have to be divisible by 8 but are {height} and {width}.'		)

										# get prompt text embeddings
										_UpperCAmelCase				:						Tuple       						=			self.tokenizer(
										    A_  ,    padding="max_length"  ,    max_length=self.tokenizer.model_max_length  ,    truncation=A_  ,    return_tensors="pt"  ,    )
										_UpperCAmelCase				:						Any       						=			self.text_encoder(text_input.input_ids.to(self.device		)		)[0]
										# duplicate text embeddings for each generation per prompt
										_UpperCAmelCase				:						Optional[int]       						=			text_embeddings.repeat_interleave(A_  ,    dim=0		)

										if clip_guidance_scale > 0:
														if clip_prompt is not None:
																		_UpperCAmelCase				:						Optional[int]       						=			self.tokenizer(
																		    A_  ,    padding="max_length"  ,    max_length=self.tokenizer.model_max_length  ,    truncation=A_  ,    return_tensors="pt"  ,    ).input_ids.to(self.device		)
														else:
																		_UpperCAmelCase				:						int       						=			text_input.input_ids.to(self.device		)
														_UpperCAmelCase				:						Tuple       						=			self.clip_model.get_text_features(A_		)
														_UpperCAmelCase				:						List[Any]       						=			text_embeddings_clip / text_embeddings_clip.norm(p=2  ,    dim=-1  ,    keepdim=A_		)
														# duplicate text embeddings clip for each generation per prompt
														_UpperCAmelCase				:						Optional[int]       						=			text_embeddings_clip.repeat_interleave(A_  ,    dim=0		)

										# here `guidance_scale` is defined analog to the guidance weight `w` of equation (2)
										# of the Imagen paper: https://arxiv.org/pdf/2205.11487.pdf . `guidance_scale = 1`
										# corresponds to doing no classifier free guidance.
										_UpperCAmelCase				:						str       						=			guidance_scale > 1.0
										# get unconditional embeddings for classifier free guidance
										if do_classifier_free_guidance:
														_UpperCAmelCase				:						Optional[int]       						=			text_input.input_ids.shape[-1]
														_UpperCAmelCase				:						List[Any]       						=			self.tokenizer([""]  ,    padding="max_length"  ,    max_length=A_  ,    return_tensors="pt"		)
														_UpperCAmelCase				:						Optional[Any]       						=			self.text_encoder(uncond_input.input_ids.to(self.device		)		)[0]
														# duplicate unconditional embeddings for each generation per prompt
														_UpperCAmelCase				:						Any       						=			uncond_embeddings.repeat_interleave(A_  ,    dim=0		)

														# For classifier free guidance, we need to do two forward passes.
														# Here we concatenate the unconditional and text embeddings into a single batch
														# to avoid doing two forward passes
														_UpperCAmelCase				:						List[Any]       						=			torch.cat([uncond_embeddings, text_embeddings]		)

										# get the initial random noise unless the user supplied it

										# Unlike in other pipelines, latents need to be generated in the target device
										# for 1-to-1 results reproducibility with the CompVis implementation.
										# However this currently doesn't work in `mps`.
										_UpperCAmelCase				:						Optional[Any]       						=			(batch_size * num_images_per_prompt, self.unet.config.in_channels, height // 8, width // 8)
										_UpperCAmelCase				:						Optional[Any]       						=			text_embeddings.dtype
										if latents is None:
														if self.device.type == "mps":
																		# randn does not work reproducibly on mps
																		_UpperCAmelCase				:						Optional[int]       						=			torch.randn(A_  ,    generator=A_  ,    device="cpu"  ,    dtype=A_		).to(
																		    self.device		)
														else:
																		_UpperCAmelCase				:						Optional[Any]       						=			torch.randn(A_  ,    generator=A_  ,    device=self.device  ,    dtype=A_		)
										else:
														if latents.shape != latents_shape:
																		raise ValueError(f'Unexpected latents shape, got {latents.shape}, expected {latents_shape}'		)
														_UpperCAmelCase				:						Tuple       						=			latents.to(self.device		)

										# set timesteps
										_UpperCAmelCase				:						List[Any]       						=			"offset" in set(inspect.signature(self.scheduler.set_timesteps		).parameters.keys()		)
										_UpperCAmelCase				:						Union[str, Any]       						=			{}
										if accepts_offset:
														_UpperCAmelCase				:						Union[str, Any]       						=			1

										self.scheduler.set_timesteps(A_  ,    **A_		)

										# Some schedulers like PNDM have timesteps as arrays
										# It's more optimized to move all timesteps to correct device beforehand
										_UpperCAmelCase				:						List[str]       						=			self.scheduler.timesteps.to(self.device		)

										# scale the initial noise by the standard deviation required by the scheduler
										_UpperCAmelCase				:						List[str]       						=			latents * self.scheduler.init_noise_sigma

										# prepare extra kwargs for the scheduler step, since not all schedulers have the same signature
										# eta (η) is only used with the DDIMScheduler, it will be ignored for other schedulers.
										# eta corresponds to η in DDIM paper: https://arxiv.org/abs/2010.02502
										# and should be between [0, 1]
										_UpperCAmelCase				:						Optional[int]       						=			"eta" in set(inspect.signature(self.scheduler.step		).parameters.keys()		)
										_UpperCAmelCase				:						Any       						=			{}
										if accepts_eta:
														_UpperCAmelCase				:						List[Any]       						=			eta

										# check if the scheduler accepts generator
										_UpperCAmelCase				:						int       						=			"generator" in set(inspect.signature(self.scheduler.step		).parameters.keys()		)
										if accepts_generator:
														_UpperCAmelCase				:						Union[str, Any]       						=			generator

										for i, t in enumerate(self.progress_bar(A_		)		):
														# expand the latents if we are doing classifier free guidance
														_UpperCAmelCase				:						Dict       						=			torch.cat([latents] * 2		) if do_classifier_free_guidance else latents
														_UpperCAmelCase				:						List[str]       						=			self.scheduler.scale_model_input(A_  ,    A_		)

														# predict the noise residual
														_UpperCAmelCase				:						Optional[Any]       						=			self.unet(A_  ,    A_  ,    encoder_hidden_states=A_		).sample

														# perform classifier free guidance
														if do_classifier_free_guidance:
																		_UpperCAmelCase						,							_UpperCAmelCase				:						List[Any]       						=			noise_pred.chunk(2		)
																		_UpperCAmelCase				:						Tuple       						=			noise_pred_uncond + guidance_scale * (noise_pred_text - noise_pred_uncond)

														# perform clip guidance
														if clip_guidance_scale > 0:
																		_UpperCAmelCase				:						Tuple       						=			(
																		    text_embeddings.chunk(2		)[1] if do_classifier_free_guidance else text_embeddings
																		)
																		_UpperCAmelCase						,							_UpperCAmelCase				:						Dict       						=			self.cond_fn(
																		    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    A_  ,    )

														# compute the previous noisy sample x_t -> x_t-1
														_UpperCAmelCase				:						Any       						=			self.scheduler.step(A_  ,    A_  ,    A_  ,    **A_		).prev_sample

										# scale and decode the image latents with vae
										_UpperCAmelCase				:						Optional[Any]       						=			1 / self.vae.config.scaling_factor * latents
										_UpperCAmelCase				:						Tuple       						=			self.vae.decode(A_		).sample

										_UpperCAmelCase				:						Tuple       						=			(image / 2 + 0.5).clamp(0  ,    1		)
										_UpperCAmelCase				:						Tuple       						=			image.cpu().permute(0  ,    2  ,    3  ,    1		).numpy()

										if output_type == "pil":
														_UpperCAmelCase				:						Union[str, Any]       						=			self.numpy_to_pil(A_		)

										if not return_dict:
														return (image, None)

										return StableDiffusionPipelineOutput(images=A_  ,    nsfw_content_detected=A_		)





from __future__ import annotations

from collections.abc import Iterable

class  a     :


						def __init__(				self  ,    A_  ,    A_		):







										'''simple docstring'''


										_UpperCAmelCase						,							_UpperCAmelCase				:						Optional[Any]       						=			float(A_		), float(A_		)


						def __eq__(				self  ,    A_		):







										'''simple docstring'''


										return self.x == other.x and self.y == other.y


						def __ne__(				self  ,    A_		):







										'''simple docstring'''


										return not self == other


						def __gt__(				self  ,    A_		):







										'''simple docstring'''


										if self.x > other.x:
														return True
										elif self.x == other.x:
														return self.y > other.y
										return False


						def __lt__(				self  ,    A_		):







										'''simple docstring'''


										return not self > other


						def __ge__(				self  ,    A_		):







										'''simple docstring'''


										if self.x > other.x:
														return True
										elif self.x == other.x:
														return self.y >= other.y
										return False


						def __le__(				self  ,    A_		):







										'''simple docstring'''


										if self.x < other.x:
														return True
										elif self.x == other.x:
														return self.y <= other.y
										return False


						def __repr__(				self		):







										'''simple docstring'''


										return f'({self.x}, {self.y})'





						def __hash__(				self		):







										'''simple docstring'''


										return hash(self.x		)







def 							__SCREAMING_SNAKE_CASE							( lowerCAmelCase:     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(lowerCAmelCase     ,					lowerCAmelCase       ):
																points.append(lowerCAmelCase       )
												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 							__SCREAMING_SNAKE_CASE							( lowerCAmelCase:     list[Point] | list[list[float]]       )      ->				list[Point]:

				if not hasattr(lowerCAmelCase     ,					"__iter__"       ):
								_UpperCAmelCase				:						Optional[Any]       						=			F'Expecting an iterable object but got an non-iterable type {points}'
								raise ValueError(lowerCAmelCase       )

				if not points:
								_UpperCAmelCase				:						str       						=			F'Expecting a list of points but got {points}'
								raise ValueError(lowerCAmelCase       )

				return _construct_points(lowerCAmelCase       )

def 							__SCREAMING_SNAKE_CASE							( lowerCAmelCase:     Point     ,					lowerCAmelCase:     Point     ,					lowerCAmelCase:     Point       )      ->				float:
				_UpperCAmelCase				:						Union[str, Any]       						=			(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 							__SCREAMING_SNAKE_CASE							( lowerCAmelCase:     list[Point]       )      ->				list[Point]:
				_UpperCAmelCase				:						Union[str, Any]       						=			sorted(_validate_input(lowerCAmelCase       )       )
				_UpperCAmelCase				:						Any       						=			len(lowerCAmelCase       )
				_UpperCAmelCase				:						Any       						=			set()

				for i in range(n - 1       ):
								for j in range(i + 1     ,					lowerCAmelCase       ):
												_UpperCAmelCase				:						Optional[int]       						=			False
												_UpperCAmelCase				:						Union[str, Any]       						=			True
												for k in range(lowerCAmelCase       ):
																if k != i and k != j:
																				_UpperCAmelCase				:						Tuple       						=			_det(points[i]     ,					points[j]     ,					points[k]       )

																				if det_k > 0:
																								_UpperCAmelCase				:						str       						=			True
																				elif det_k < 0:
																								_UpperCAmelCase				:						Optional[Any]       						=			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				:						Any       						=			False
																												break

																if points_left_of_ij and points_right_of_ij:
																				_UpperCAmelCase				:						int       						=			False
																				break

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

				return sorted(lowerCAmelCase       )

def 							__SCREAMING_SNAKE_CASE							( lowerCAmelCase:     list[Point]       )      ->				list[Point]:
				_UpperCAmelCase				:						List[Any]       						=			sorted(_validate_input(lowerCAmelCase       )       )
				_UpperCAmelCase				:						int       						=			len(lowerCAmelCase       )

				# 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				:						Tuple       						=			points[0]
				_UpperCAmelCase				:						Optional[Any]       						=			points[n - 1]

				_UpperCAmelCase				:						Optional[Any]       						=			{left_most_point, right_most_point}
				_UpperCAmelCase				:						Tuple       						=			[]
				_UpperCAmelCase				:						Optional[Any]       						=			[]

				for i in range(1     ,					n - 1       ):
								_UpperCAmelCase				:						Optional[int]       						=			_det(lowerCAmelCase     ,					lowerCAmelCase     ,					points[i]       )

								if det > 0:
												upper_hull.append(points[i]       )
								elif det < 0:
												lower_hull.append(points[i]       )

				_construct_hull(lowerCAmelCase     ,					lowerCAmelCase     ,					lowerCAmelCase     ,					lowerCAmelCase       )
				_construct_hull(lowerCAmelCase     ,					lowerCAmelCase     ,					lowerCAmelCase     ,					lowerCAmelCase       )

				return sorted(lowerCAmelCase       )

def 							__SCREAMING_SNAKE_CASE							( lowerCAmelCase:     list[Point]     ,					lowerCAmelCase:     Point     ,					lowerCAmelCase:     Point     ,					lowerCAmelCase:     set[Point]       )      ->				None:
				if points:
								_UpperCAmelCase				:						List[str]       						=			None
								_UpperCAmelCase				:						Optional[int]       						=			float("-inf"       )
								_UpperCAmelCase				:						Dict       						=			[]

								for p in points:
												_UpperCAmelCase				:						int       						=			_det(lowerCAmelCase     ,					lowerCAmelCase     ,					lowerCAmelCase       )

												if det > 0:
																candidate_points.append(lowerCAmelCase       )

																if det > extreme_point_distance:
																				_UpperCAmelCase				:						Dict       						=			det
																				_UpperCAmelCase				:						Union[str, Any]       						=			p

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

def 							__SCREAMING_SNAKE_CASE							( lowerCAmelCase:     list[Point]       )      ->				list[Point]:
				_UpperCAmelCase				:						int       						=			sorted(_validate_input(lowerCAmelCase       )       )
				_UpperCAmelCase				:						Any       						=			len(lowerCAmelCase       )

				_UpperCAmelCase				:						List[Any]       						=			points[:2]
				for i in range(2     ,					lowerCAmelCase       ):
								_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				:						Optional[int]       						=			points[i]
				i += 1

				for j in range(lowerCAmelCase     ,					lowerCAmelCase       ):
								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(lowerCAmelCase       ) > 3 else convex_hull       )

def 							__SCREAMING_SNAKE_CASE							( )      ->				List[str]:
				_UpperCAmelCase				:						Union[str, 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				:						int       						=			convex_hull_bf(lowerCAmelCase       )

				_UpperCAmelCase				:						Union[str, Any]       						=			convex_hull_recursive(lowerCAmelCase       )
				assert results_bf == results_recursive

				_UpperCAmelCase				:						int       						=			convex_hull_melkman(lowerCAmelCase       )
				assert results_bf == results_melkman

				print(lowerCAmelCase       )


if __name__ == "__main__":
					main()


