"""simple docstring"""







import argparse
import os

import align
import numpy as np
import requests
import tensorflow as tf
import torch
from PIL import Image
from tokenizer import Tokenizer

from transformers import (
    AlignConfig,
    AlignModel,
    AlignProcessor,
    BertConfig,
    BertTokenizer,
    EfficientNetConfig,
    EfficientNetImageProcessor,
)
from transformers.utils import logging


logging.set_verbosity_info()
_a	:	Dict=					logging.get_logger(__name__)
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Optional[int]    )				->     Tuple:

	'''simple docstring'''





	__snake_case     :				str 						=					tf.image.resize(_lowercase     ,				(3_46, 3_46)    )
	__snake_case     :				List[Any] 						=					tf.image.crop_to_bounding_box(_lowercase     ,				(3_46 - 2_89) // 2     ,				(3_46 - 2_89) // 2     ,				2_89     ,				2_89    )
	return image
def     __UpperCAmelCase							(       )				->     str:

	'''simple docstring'''





	__snake_case     :				Optional[Any] 						=					EfficientNetConfig.from_pretrained('google/efficientnet-b7'    )
	__snake_case     :				int 						=					2_89
	__snake_case     :				List[Any] 						=					6_40
	__snake_case     :				Optional[Any] 						=					{"""0""": """LABEL_0""", """1""": """LABEL_1"""}
	__snake_case     :				str 						=					{"""LABEL_0""": 0, """LABEL_1""": 1}
	__snake_case     :				Dict 						=					[]

	__snake_case     :				int 						=					BertConfig()
	__snake_case     :				Optional[Any] 						=					AlignConfig.from_text_vision_configs(
	    text_config=_lowercase     ,				vision_config=_lowercase     ,				projection_dim=6_40    )
	return config
def     __UpperCAmelCase							(       )				->     int:

	'''simple docstring'''





	__snake_case     :				List[str] 						=					"""http://images.cocodataset.org/val2017/000000039769.jpg"""
	__snake_case     :				Union[str, Any] 						=					Image.open(requests.get(_lowercase     ,				stream=_lowercase    ).raw    )
	return im
def     __UpperCAmelCase							(       )				->     int:

	'''simple docstring'''





	__snake_case     :				Dict 						=					EfficientNetImageProcessor(
	    do_center_crop=_lowercase     ,				rescale_factor=1 / 127.5     ,				rescale_offset=_lowercase     ,				do_normalize=_lowercase     ,				include_top=_lowercase     ,				resample=Image.BILINEAR     ,				)
	__snake_case     :				int 						=					BertTokenizer.from_pretrained('bert-base-uncased'    )
	__snake_case     :				Optional[int] 						=					64
	__snake_case     :				Dict 						=					AlignProcessor(image_processor=_lowercase     ,				tokenizer=_lowercase    )
	return processor
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Optional[int]    )				->     Union[str, Any]:

	'''simple docstring'''





	__snake_case     :				int 						=					[v.split('_'    )[0].split('block'    )[1] for v in original_param_names if v.startswith('block'    )]
	__snake_case     :				Dict 						=					list(set(_lowercase    )    )
	__snake_case     :				str 						=					sorted(_lowercase    )
	__snake_case     :				Any 						=					len(_lowercase    )
	__snake_case     :				List[Any] 						=					{b: str(_lowercase    ) for b, i in zip(_lowercase     ,				range(_lowercase    )    )}

	__snake_case     :				List[Any] 						=					[]
	rename_keys.append(('stem_conv/kernel:0', 'embeddings.convolution.weight')    )
	rename_keys.append(('stem_bn/gamma:0', 'embeddings.batchnorm.weight')    )
	rename_keys.append(('stem_bn/beta:0', 'embeddings.batchnorm.bias')    )
	rename_keys.append(('stem_bn/moving_mean:0', 'embeddings.batchnorm.running_mean')    )
	rename_keys.append(('stem_bn/moving_variance:0', 'embeddings.batchnorm.running_var')    )

	for b in block_names:
		__snake_case     :				Union[str, Any] 						=					block_name_mapping[b]
		rename_keys.append((F"block{b}_expand_conv/kernel:0", F"encoder.blocks.{hf_b}.expansion.expand_conv.weight")    )
		rename_keys.append((F"block{b}_expand_bn/gamma:0", F"encoder.blocks.{hf_b}.expansion.expand_bn.weight")    )
		rename_keys.append((F"block{b}_expand_bn/beta:0", F"encoder.blocks.{hf_b}.expansion.expand_bn.bias")    )
		rename_keys.append(
		    (F"block{b}_expand_bn/moving_mean:0", F"encoder.blocks.{hf_b}.expansion.expand_bn.running_mean")    )
		rename_keys.append(
		    (F"block{b}_expand_bn/moving_variance:0", F"encoder.blocks.{hf_b}.expansion.expand_bn.running_var")    )
		rename_keys.append(
		    (F"block{b}_dwconv/depthwise_kernel:0", F"encoder.blocks.{hf_b}.depthwise_conv.depthwise_conv.weight")    )
		rename_keys.append((F"block{b}_bn/gamma:0", F"encoder.blocks.{hf_b}.depthwise_conv.depthwise_norm.weight")    )
		rename_keys.append((F"block{b}_bn/beta:0", F"encoder.blocks.{hf_b}.depthwise_conv.depthwise_norm.bias")    )
		rename_keys.append(
		    (F"block{b}_bn/moving_mean:0", F"encoder.blocks.{hf_b}.depthwise_conv.depthwise_norm.running_mean")    )
		rename_keys.append(
		    (F"block{b}_bn/moving_variance:0", F"encoder.blocks.{hf_b}.depthwise_conv.depthwise_norm.running_var")    )

		rename_keys.append((F"block{b}_se_reduce/kernel:0", F"encoder.blocks.{hf_b}.squeeze_excite.reduce.weight")    )
		rename_keys.append((F"block{b}_se_reduce/bias:0", F"encoder.blocks.{hf_b}.squeeze_excite.reduce.bias")    )
		rename_keys.append((F"block{b}_se_expand/kernel:0", F"encoder.blocks.{hf_b}.squeeze_excite.expand.weight")    )
		rename_keys.append((F"block{b}_se_expand/bias:0", F"encoder.blocks.{hf_b}.squeeze_excite.expand.bias")    )
		rename_keys.append(
		    (F"block{b}_project_conv/kernel:0", F"encoder.blocks.{hf_b}.projection.project_conv.weight")    )
		rename_keys.append((F"block{b}_project_bn/gamma:0", F"encoder.blocks.{hf_b}.projection.project_bn.weight")    )
		rename_keys.append((F"block{b}_project_bn/beta:0", F"encoder.blocks.{hf_b}.projection.project_bn.bias")    )
		rename_keys.append(
		    (F"block{b}_project_bn/moving_mean:0", F"encoder.blocks.{hf_b}.projection.project_bn.running_mean")    )
		rename_keys.append(
		    (F"block{b}_project_bn/moving_variance:0", F"encoder.blocks.{hf_b}.projection.project_bn.running_var")    )

	__snake_case     :				Union[str, Any] 						=					{}
	for item in rename_keys:
		if item[0] in original_param_names:
			__snake_case     :				Union[str, Any] 						=					"""vision_model.""" + item[1]

    # BERT text encoder
	__snake_case     :				int 						=					[]
	__snake_case     :				Union[str, Any] 						=					"""tf_bert_model/bert"""
	__snake_case     :				Optional[int] 						=					"""text_model"""
	for i in range(12    ):
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/attention/self/query/kernel:0",
		        F"{new}.encoder.layer.{i}.attention.self.query.weight",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/attention/self/query/bias:0",
		        F"{new}.encoder.layer.{i}.attention.self.query.bias",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/attention/self/key/kernel:0",
		        F"{new}.encoder.layer.{i}.attention.self.key.weight",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/attention/self/key/bias:0",
		        F"{new}.encoder.layer.{i}.attention.self.key.bias",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/attention/self/value/kernel:0",
		        F"{new}.encoder.layer.{i}.attention.self.value.weight",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/attention/self/value/bias:0",
		        F"{new}.encoder.layer.{i}.attention.self.value.bias",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/attention/output/dense/kernel:0",
		        F"{new}.encoder.layer.{i}.attention.output.dense.weight",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/attention/output/dense/bias:0",
		        F"{new}.encoder.layer.{i}.attention.output.dense.bias",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/attention/output/LayerNorm/gamma:0",
		        F"{new}.encoder.layer.{i}.attention.output.LayerNorm.weight",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/attention/output/LayerNorm/beta:0",
		        F"{new}.encoder.layer.{i}.attention.output.LayerNorm.bias",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/intermediate/dense/kernel:0",
		        F"{new}.encoder.layer.{i}.intermediate.dense.weight",
		    )    )
		rename_keys.append(
		    (
		        F"{old}/encoder/layer_._{i}/intermediate/dense/bias:0",
		        F"{new}.encoder.layer.{i}.intermediate.dense.bias",
		    )    )
		rename_keys.append(
		    (F"{old}/encoder/layer_._{i}/output/dense/kernel:0", F"{new}.encoder.layer.{i}.output.dense.weight")    )
		rename_keys.append(
		    (F"{old}/encoder/layer_._{i}/output/dense/bias:0", F"{new}.encoder.layer.{i}.output.dense.bias")    )
		rename_keys.append(
		    (F"{old}/encoder/layer_._{i}/output/LayerNorm/gamma:0", F"{new}.encoder.layer.{i}.output.LayerNorm.weight")    )
		rename_keys.append(
		    (F"{old}/encoder/layer_._{i}/output/LayerNorm/beta:0", F"{new}.encoder.layer.{i}.output.LayerNorm.bias")    )

	rename_keys.append((F"{old}/embeddings/word_embeddings/weight:0", F"{new}.embeddings.word_embeddings.weight")    )
	rename_keys.append(
	    (F"{old}/embeddings/position_embeddings/embeddings:0", F"{new}.embeddings.position_embeddings.weight")    )
	rename_keys.append(
	    (F"{old}/embeddings/token_type_embeddings/embeddings:0", F"{new}.embeddings.token_type_embeddings.weight")    )
	rename_keys.append((F"{old}/embeddings/LayerNorm/gamma:0", F"{new}.embeddings.LayerNorm.weight")    )
	rename_keys.append((F"{old}/embeddings/LayerNorm/beta:0", F"{new}.embeddings.LayerNorm.bias")    )

	rename_keys.append((F"{old}/pooler/dense/kernel:0", F"{new}.pooler.dense.weight")    )
	rename_keys.append((F"{old}/pooler/dense/bias:0", F"{new}.pooler.dense.bias")    )
	rename_keys.append(('dense/kernel:0', 'text_projection.weight')    )
	rename_keys.append(('dense/bias:0', 'text_projection.bias')    )
	rename_keys.append(('dense/bias:0', 'text_projection.bias')    )
	rename_keys.append(('temperature:0', 'temperature')    )

	for item in rename_keys:
		if item[0] in original_param_names:
			__snake_case     :				Union[str, Any] 						=					item[1]
	return key_mapping
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Any     ,				UpperCAmelCase_       :							List[Any]     ,				UpperCAmelCase_       :							str    )				->     List[str]:

	'''simple docstring'''





	list(hf_params.keys()    )

	for key, value in tf_params.items():
		if key not in key_mapping:
			continue

		__snake_case     :				Any 						=					key_mapping[key]
		if "_conv" in key and "kernel" in key:
			__snake_case     :				int 						=					torch.from_numpy(_lowercase    ).permute(3     ,				2     ,				0     ,				1    )
		elif "embeddings" in key:
			__snake_case     :				str 						=					torch.from_numpy(_lowercase    )
		elif "depthwise_kernel" in key:
			__snake_case     :				Tuple 						=					torch.from_numpy(_lowercase    ).permute(2     ,				3     ,				0     ,				1    )
		elif "kernel" in key:
			__snake_case     :				List[str] 						=					torch.from_numpy(np.transpose(_lowercase    )    )
		elif "temperature" in key:
			__snake_case     :				Dict 						=					value
		elif "bn/gamma" or "bn/beta" in key:
			__snake_case     :				Any 						=					torch.from_numpy(np.transpose(_lowercase    )    ).squeeze()
		else:
			__snake_case     :				Dict 						=					torch.from_numpy(_lowercase    )

		# Replace HF parameters with original TF model parameters
		hf_params[hf_key].copy_(_lowercase    )
@torch.no_grad()
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Optional[int]     ,				UpperCAmelCase_       :							Any     ,				UpperCAmelCase_       :							List[str]     ,				UpperCAmelCase_       :							Optional[Any]    )				->     Any:

	'''simple docstring'''





	__snake_case     :				Dict 						=					64
	__snake_case     :				Tuple 						=					Tokenizer(_lowercase    )
	__snake_case     :				Tuple 						=					align.Align('efficientnet-b7'     ,				'bert-base'     ,				6_40     ,				_lowercase     ,				tok.get_vocab_size()    )
	original_model.compile()
	original_model.load_weights(_lowercase    )

	__snake_case     :				int 						=					original_model.trainable_variables
	__snake_case     :				str 						=					original_model.non_trainable_variables
	__snake_case     :				List[Any] 						=					{param.name: param.numpy() for param in tf_params}
	for param in tf_non_train_params:
		__snake_case     :				List[str] 						=					param.numpy()
	__snake_case     :				List[Any] 						=					list(tf_params.keys()    )

	# Load HuggingFace model
	__snake_case     :				Tuple 						=					get_align_config()
	__snake_case     :				str 						=					AlignModel(_lowercase    ).eval()
	__snake_case     :				Optional[Any] 						=					hf_model.state_dict()

	# Create src-to-dst parameter name mapping dictionary
	print('Converting parameters...'    )
	__snake_case     :				Optional[Any] 						=					rename_keys(_lowercase    )
	replace_params(_lowercase     ,				_lowercase     ,				_lowercase    )

	# Initialize processor
	__snake_case     :				List[str] 						=					get_processor()
	__snake_case     :				Optional[Any] 						=					processor(
	    images=prepare_img()     ,				text='A picture of a cat'     ,				padding='max_length'     ,				max_length=64     ,				return_tensors='pt'    )

	# HF model inference
	hf_model.eval()
	with torch.no_grad():
		__snake_case     :				Optional[int] 						=					hf_model(**_lowercase    )

	__snake_case     :				List[Any] 						=					outputs.image_embeds.detach().numpy()
	__snake_case     :				Union[str, Any] 						=					outputs.text_embeds.detach().numpy()

	# Original model inference
	__snake_case     :				List[Any] 						=					False
	__snake_case     :				List[str] 						=					EfficientNetImageProcessor(
	    do_center_crop=_lowercase     ,				do_rescale=_lowercase     ,				do_normalize=_lowercase     ,				include_top=_lowercase     ,				resample=Image.BILINEAR     ,				)
	__snake_case     :				List[str] 						=					tf_image_processor(images=prepare_img()     ,				return_tensors='tf'     ,				data_format='channels_last'    )["""pixel_values"""]
	__snake_case     :				int 						=					tok(tf.constant(['A picture of a cat']    )    )

	__snake_case     :				Any 						=					original_model.image_encoder(_lowercase     ,				training=_lowercase    )
	__snake_case     :				Dict 						=					original_model.text_encoder(_lowercase     ,				training=_lowercase    )

	__snake_case     :				Any 						=					tf.nn.la_normalize(_lowercase     ,				axis=-1    )
	__snake_case     :				Any 						=					tf.nn.la_normalize(_lowercase     ,				axis=-1    )

	# Check whether original and HF model outputs match  -> np.allclose
	if not np.allclose(_lowercase     ,				_lowercase     ,				atol=1E-3    ):
		raise ValueError('The predicted image features are not the same.'    )
	if not np.allclose(_lowercase     ,				_lowercase     ,				atol=1E-3    ):
		raise ValueError('The predicted text features are not the same.'    )
	print('Model outputs match!'    )

	if save_model:
		# Create folder to save model
		if not os.path.isdir(_lowercase    ):
			os.mkdir(_lowercase    )
		# Save converted model and image processor
		hf_model.save_pretrained(_lowercase    )
		processor.save_pretrained(_lowercase    )

	if push_to_hub:
		# Push model and image processor to hub
		print('Pushing converted ALIGN to the hub...'    )
		processor.push_to_hub('align-base'    )
		hf_model.push_to_hub('align-base'    )


if __name__ == "__main__":
	_a	:	str=					argparse.ArgumentParser()
	# Required parameters
	parser.add_argument(
	    "--checkpoint_path",
	    default="./weights/model-weights",
	    type=str,
	    help="Path to the pretrained TF ALIGN checkpoint.",
	)
	parser.add_argument(
	    "--pytorch_dump_folder_path",
	    default="hf_model",
	    type=str,
	    help="Path to the output PyTorch model directory.",
	)
	parser.add_argument("--save_model", action="store_true", help="Save model to local")
	parser.add_argument("--push_to_hub", action="store_true", help="Push model and image processor to the hub")

	_a	:	Any=					parser.parse_args()
	convert_align_checkpoint(args.checkpoint_path, args.pytorch_dump_folder_path, args.save_model, args.push_to_hub)










'''simple docstring'''




from __future__ import annotations

from collections.abc import Iterable

class      UpperCamelCase_					:





	def __init__(    self						,						A						,						A       )     ->     int:
								UpperCAmelCase	,	UpperCAmelCase	:						Any					=						float(A       ), float(A       )





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





	def __ne__(    self						,						A       )     ->     Dict:
								return not self == other





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





	def __lt__(    self						,						A       )     ->     str:
								return not self > other





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





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





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






	def __hash__(    self       )     ->     List[str]:
								return hash(self.x       )




def  __lowerCamelCase    (   _lowercase      ,							) ->     list[Point]:
							UpperCAmelCase	:						list[Point]					=						[]
							if list_of_tuples:
														for p in list_of_tuples:
																					if isinstance(_lowercase      ,							_lowercase						):
																												points.append(_lowercase						)
																					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  __lowerCamelCase    (   _lowercase						) ->     list[Point]:

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

							if not points:
														UpperCAmelCase	:						Optional[int]					=						F'''Expecting a list of points but got {points}'''
														raise ValueError(_lowercase						)

							return _construct_points(_lowercase						)



def  __lowerCamelCase    (   _lowercase      ,							_lowercase      ,							_lowercase						) ->     float:
							UpperCAmelCase	:						Dict					=						(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  __lowerCamelCase    (   _lowercase						) ->     list[Point]:
							UpperCAmelCase	:						Optional[int]					=						sorted(_validate_input(_lowercase						)						)
							UpperCAmelCase	:						int					=						len(_lowercase						)
							UpperCAmelCase	:						Any					=						set()

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

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

																												if points_left_of_ij and points_right_of_ij:
																																			UpperCAmelCase	:						Union[str, Any]					=						False
																																			break

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

							return sorted(_lowercase						)



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

							# 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[str]					=						points[0]
							UpperCAmelCase	:						Union[str, Any]					=						points[n - 1]

							UpperCAmelCase	:						int					=						{left_most_point, right_most_point}
							UpperCAmelCase	:						Dict					=						[]
							UpperCAmelCase	:						Any					=						[]

							for i in range(1      ,							n - 1						):
														UpperCAmelCase	:						Any					=						_det(_lowercase      ,							_lowercase      ,							points[i]						)

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

							_construct_hull(_lowercase      ,							_lowercase      ,							_lowercase      ,							_lowercase						)
							_construct_hull(_lowercase      ,							_lowercase      ,							_lowercase      ,							_lowercase						)

							return sorted(_lowercase						)



def  __lowerCamelCase    (   _lowercase      ,							_lowercase      ,							_lowercase      ,							_lowercase						) ->     None:
							if points:
														UpperCAmelCase	:						Union[str, Any]					=						None
														UpperCAmelCase	:						int					=						float("""-inf"""						)
														UpperCAmelCase	:						Tuple					=						[]

														for p in points:
																					UpperCAmelCase	:						List[Any]					=						_det(_lowercase      ,							_lowercase      ,							_lowercase						)

																					if det > 0:
																												candidate_points.append(_lowercase						)

																												if det > extreme_point_distance:
																																			UpperCAmelCase	:						List[str]					=						det
																																			UpperCAmelCase	:						Optional[Any]					=						p

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



def  __lowerCamelCase    (   _lowercase						) ->     list[Point]:
							UpperCAmelCase	:						Any					=						sorted(_validate_input(_lowercase						)						)
							UpperCAmelCase	:						Union[str, Any]					=						len(_lowercase						)

							UpperCAmelCase	:						Dict					=						points[:2]
							for i in range(2      ,							_lowercase						):
														UpperCAmelCase	:						Dict					=						_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	:						Dict					=						points[i]
							i += 1

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



def  __lowerCamelCase    (   ) ->     Tuple:
							UpperCAmelCase	:						Tuple					=						[
							    (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	:						Tuple					=						convex_hull_bf(_lowercase						)

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

							UpperCAmelCase	:						Union[str, Any]					=						convex_hull_melkman(_lowercase						)
							assert results_bf == results_melkman

							print(_lowercase						)


if __name__ == "__main__":
							main()

