import inspect
import unittest

from transformers import is_torch_available, is_vision_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_vision, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
     import torch

     from transformers import MODEL_MAPPING, GLPNConfig, GLPNForDepthEstimation, GLPNModel
     from transformers.models.glpn.modeling_glpn import GLPN_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
     from PIL import Image

     from transformers import GLPNImageProcessor







class 			SCREAMING_SNAKE_CASE__ (   __UpperCamelCase  ):

       def        snake_case__  (				self :			Union[str, Any]       ):
           __snake_case    :							int             =  self.config_class(**self.inputs_dict       )
           self.parent.assertTrue(hasattr(A_       ,       """hidden_sizes"""       )       )
           self.parent.assertTrue(hasattr(A_       ,       """num_attention_heads"""       )       )
           self.parent.assertTrue(hasattr(A_       ,       """num_encoder_blocks"""       )       )







class 			SCREAMING_SNAKE_CASE__ :

       def __init__(				self :			Optional[int]       ,       _lowerCAmelCase :			Union[str, Any]       ,       _lowerCAmelCase :			List[str]=13       ,       _lowerCAmelCase :			Union[str, Any]=64       ,       _lowerCAmelCase :			Any=3       ,       _lowerCAmelCase :			Optional[int]=4       ,       _lowerCAmelCase :			Union[str, Any]=[2, 2, 2, 2]       ,       _lowerCAmelCase :			Tuple=[8, 4, 2, 1]       ,       _lowerCAmelCase :			Optional[int]=[16, 32, 64, 1_28]       ,       _lowerCAmelCase :			Dict=[1, 4, 8, 16]       ,       _lowerCAmelCase :			Optional[Any]=[1, 2, 4, 8]       ,       _lowerCAmelCase :			Any=True       ,       _lowerCAmelCase :			Any=True       ,       _lowerCAmelCase :			int="gelu"       ,       _lowerCAmelCase :			Union[str, Any]=0.1       ,       _lowerCAmelCase :			Optional[Any]=0.1       ,       _lowerCAmelCase :			str=0.02       ,       _lowerCAmelCase :			int=16       ,       _lowerCAmelCase :			Tuple=3       ,       _lowerCAmelCase :			Optional[int]=None       ,       ):
           __snake_case    :							int             =  parent
           __snake_case    :							List[str]             =  batch_size
           __snake_case    :							Dict             =  image_size
           __snake_case    :							Dict             =  num_channels
           __snake_case    :							List[Any]             =  num_encoder_blocks
           __snake_case    :							Dict             =  sr_ratios
           __snake_case    :							str             =  depths
           __snake_case    :							Union[str, Any]             =  hidden_sizes
           __snake_case    :							Any             =  downsampling_rates
           __snake_case    :							str             =  num_attention_heads
           __snake_case    :							Optional[int]             =  is_training
           __snake_case    :							Any             =  use_labels
           __snake_case    :							Union[str, Any]             =  hidden_act
           __snake_case    :							Dict             =  hidden_dropout_prob
           __snake_case    :							str             =  attention_probs_dropout_prob
           __snake_case    :							Optional[Any]             =  initializer_range
           __snake_case    :							List[Any]             =  decoder_hidden_size
           __snake_case    :							List[str]             =  num_labels
           __snake_case    :							Tuple             =  scope

       def        snake_case__  (				self :			List[Any]       ):
           __snake_case    :							List[str]             =  floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]       )

           __snake_case    :							str             =  None
           if self.use_labels:
               __snake_case    :							str             =  ids_tensor([self.batch_size, self.image_size, self.image_size]       ,       self.num_labels       )

           __snake_case    :							Union[str, Any]             =  self.get_config()
           return config, pixel_values, labels

       def        snake_case__  (				self :			List[Any]       ):
           return GLPNConfig(
               image_size=self.image_size       ,       num_channels=self.num_channels       ,       num_encoder_blocks=self.num_encoder_blocks       ,       depths=self.depths       ,       hidden_sizes=self.hidden_sizes       ,       num_attention_heads=self.num_attention_heads       ,       hidden_act=self.hidden_act       ,       hidden_dropout_prob=self.hidden_dropout_prob       ,       attention_probs_dropout_prob=self.attention_probs_dropout_prob       ,       initializer_range=self.initializer_range       ,       decoder_hidden_size=self.decoder_hidden_size       ,       )

       def        snake_case__  (				self :			str       ,       _lowerCAmelCase :			Any       ,       _lowerCAmelCase :			Optional[Any]       ,       _lowerCAmelCase :			int       ):
           __snake_case    :							List[str]             =  GLPNModel(config=A_       )
           model.to(A_       )
           model.eval()
           __snake_case    :							Union[str, Any]             =  model(A_       )
           __snake_case    :							List[str]             =  self.image_size // (self.downsampling_rates[-1] * 2)
           self.parent.assertEqual(
               result.last_hidden_state.shape       ,       (self.batch_size, self.hidden_sizes[-1], expected_height, expected_width)       )

       def        snake_case__  (				self :			Union[str, Any]       ,       _lowerCAmelCase :			Union[str, Any]       ,       _lowerCAmelCase :			Tuple       ,       _lowerCAmelCase :			Any       ):
           __snake_case    :							str             =  self.num_labels
           __snake_case    :							Dict             =  GLPNForDepthEstimation(A_       )
           model.to(A_       )
           model.eval()
           __snake_case    :							Dict             =  model(A_       )
           self.parent.assertEqual(result.predicted_depth.shape       ,       (self.batch_size, self.image_size, self.image_size)       )
           __snake_case    :							Tuple             =  model(A_       ,       labels=A_       )
           self.parent.assertEqual(result.predicted_depth.shape       ,       (self.batch_size, self.image_size, self.image_size)       )





       def        snake_case__  (				self :			Dict       ):
           __snake_case    :							Dict             =  self.prepare_config_and_inputs()
           __snake_case    :							str             =  config_and_inputs
           __snake_case    :							Dict             =  {"pixel_values": pixel_values}
           return config, inputs_dict







@require_torch
class 			SCREAMING_SNAKE_CASE__ (   __UpperCamelCase					,				__UpperCamelCase					,				unittest.TestCase  ):
       A				:     Union[str, Any]					    =     (GLPNModel, GLPNForDepthEstimation) if is_torch_available() else ()
       A				:     Tuple					    =     (
           {"depth-estimation": GLPNForDepthEstimation, "feature-extraction": GLPNModel} if is_torch_available() else {}
       )

       A				:     Tuple					    =     False
       A				:     Union[str, Any]					    =     False
       A				:     int					    =     False

       def        snake_case__  (				self :			Optional[Any]       ):
           __snake_case    :							Tuple             =  GLPNModelTester(self       )
           __snake_case    :							str             =  GLPNConfigTester(self       ,       config_class=A_       )

       def        snake_case__  (				self :			List[Any]       ):
           self.config_tester.run_common_tests()

       def        snake_case__  (				self :			Dict       ):
           __snake_case    :							List[str]             =  self.model_tester.prepare_config_and_inputs()
           self.model_tester.create_and_check_model(*A_       )

       def        snake_case__  (				self :			str       ):
           __snake_case    :							Union[str, Any]             =  self.model_tester.prepare_config_and_inputs()
           self.model_tester.create_and_check_for_depth_estimation(*A_       )

       @unittest.skip("""GLPN does not use inputs_embeds"""       )
       def        snake_case__  (				self :			str       ):
           pass

       @unittest.skip("""GLPN does not have get_input_embeddings method and get_output_embeddings methods"""       )
       def        snake_case__  (				self :			List[str]       ):
           pass

       def        snake_case__  (				self :			Any       ):
           __snake_case    :							Any             =  self.model_tester.prepare_config_and_inputs_for_common()

           for model_class in self.all_model_classes:
               __snake_case    :							Any             =  model_class(A_       )
               __snake_case    :							Optional[Any]             =  inspect.signature(model.forward       )
               # signature.parameters is an OrderedDict => so arg_names order is deterministic
               __snake_case    :							int             =  [*signature.parameters.keys()]

               __snake_case    :							int             =  ["pixel_values"]
               self.assertListEqual(arg_names[:1]       ,       A_       )

       def        snake_case__  (				self :			int       ):
           __snake_case    :							str             =  self.model_tester.prepare_config_and_inputs_for_common()
           __snake_case    :							Tuple             =  True

           for model_class in self.all_model_classes:
               __snake_case    :							Tuple             =  True
               __snake_case    :							Any             =  False
               __snake_case    :							Union[str, Any]             =  True
               __snake_case    :							Any             =  model_class(A_       )
               model.to(A_       )
               model.eval()
               with torch.no_grad():
                   __snake_case    :							Union[str, Any]             =  model(**self._prepare_for_class(A_       ,       A_       )       )
               __snake_case    :							List[Any]             =  outputs.attentions

               __snake_case    :							str             =  sum(self.model_tester.depths       )
               self.assertEqual(len(A_       )       ,       A_       )

               # check that output_attentions also work using config
               del inputs_dict["output_attentions"]
               __snake_case    :							Optional[Any]             =  True
               __snake_case    :							Dict             =  model_class(A_       )
               model.to(A_       )
               model.eval()
               with torch.no_grad():
                   __snake_case    :							List[Any]             =  model(**self._prepare_for_class(A_       ,       A_       )       )
               __snake_case    :							Optional[Any]             =  outputs.attentions

               self.assertEqual(len(A_       )       ,       A_       )

               # verify the first attentions (first block, first layer)
               __snake_case    :							List[str]             =  (self.model_tester.image_size // 4) ** 2
               __snake_case    :							Union[str, Any]             =  (self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
               self.assertListEqual(
                   list(attentions[0].shape[-3:]       )       ,       [self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]       ,       )

               # verify the last attentions (last block, last layer)
               __snake_case    :							Dict             =  (self.model_tester.image_size // 32) ** 2
               __snake_case    :							Optional[Any]             =  (self.model_tester.image_size // (32 * self.model_tester.sr_ratios[-1])) ** 2
               self.assertListEqual(
                   list(attentions[-1].shape[-3:]       )       ,       [self.model_tester.num_attention_heads[-1], expected_seq_len, expected_reduced_seq_len]       ,       )
               __snake_case    :							Any             =  len(A_       )

               # Check attention is always last and order is fine
               __snake_case    :							int             =  True
               __snake_case    :							Dict             =  True
               __snake_case    :							Optional[Any]             =  model_class(A_       )
               model.to(A_       )
               model.eval()
               with torch.no_grad():
                   __snake_case    :							Dict             =  model(**self._prepare_for_class(A_       ,       A_       )       )

               self.assertEqual(out_len + 1       ,       len(A_       )       )

               __snake_case    :							Optional[Any]             =  outputs.attentions

               self.assertEqual(len(A_       )       ,       A_       )
               # verify the first attentions (first block, first layer)
               __snake_case    :							int             =  (self.model_tester.image_size // 4) ** 2
               __snake_case    :							Any             =  (self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
               self.assertListEqual(
                   list(self_attentions[0].shape[-3:]       )       ,       [self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]       ,       )

       def        snake_case__  (				self :			List[Any]       ):


           def check_hidden_states_output(_lowerCAmelCase :			Optional[Any]       ,       _lowerCAmelCase :			Dict       ,       _lowerCAmelCase :			int       ):
               __snake_case    :							Union[str, Any]             =  model_class(A_       )
               model.to(A_       )
               model.eval()

               with torch.no_grad():
                   __snake_case    :							Optional[Any]             =  model(**self._prepare_for_class(A_       ,       A_       )       )

               __snake_case    :							Any             =  outputs.hidden_states

               __snake_case    :							Tuple             =  self.model_tester.num_encoder_blocks
               self.assertEqual(len(A_       )       ,       A_       )

               # verify the first hidden states (first block)
               self.assertListEqual(
                   list(hidden_states[0].shape[-3:]       )       ,       [
                       self.model_tester.hidden_sizes[0],
                       self.model_tester.image_size // 4,
                       self.model_tester.image_size // 4,
                   ]       ,       )

           __snake_case    :							List[Any]             =  self.model_tester.prepare_config_and_inputs_for_common()

           for model_class in self.all_model_classes:
               __snake_case    :							str             =  True
               check_hidden_states_output(A_       ,       A_       ,       A_       )

               # check that output_hidden_states also work using config
               del inputs_dict["output_hidden_states"]
               __snake_case    :							Optional[int]             =  True

               check_hidden_states_output(A_       ,       A_       ,       A_       )

       def        snake_case__  (				self :			str       ):


           if not self.model_tester.is_training:
               return

           __snake_case    :							str             =  self.model_tester.prepare_config_and_inputs_for_common()
           __snake_case    :							List[Any]             =  True

           for model_class in self.all_model_classes:
               if model_class in get_values(A_       ):
                   continue
               # TODO: remove the following 3 lines once we have a MODEL_FOR_DEPTH_ESTIMATION_MAPPING
               # this can then be incorporated into _prepare_for_class in test_modeling_common.py
               if model_class.__name__ == "GLPNForDepthEstimation":
                   __snake_case    :							int             =  inputs_dict["pixel_values"].shape
                   __snake_case    :							Dict             =  torch.zeros(
                       [self.model_tester.batch_size, height, width]       ,       device=A_       ).long()
               __snake_case    :							Optional[int]             =  model_class(A_       )
               model.to(A_       )
               model.train()
               __snake_case    :							Tuple             =  self._prepare_for_class(A_       ,       A_       ,       return_labels=A_       )
               __snake_case    :							Any             =  model(**A_       ).loss
               loss.backward()





       @slow
       def        snake_case__  (				self :			Dict       ):


           for model_name in GLPN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
               __snake_case    :							Optional[Any]             =  GLPNModel.from_pretrained(A_       )
               self.assertIsNotNone(A_       )







def  __lowerCAmelCase							(						):







    '''simple docstring'''
    __snake_case    :							List[Any]             =  Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""					)
    return image







@require_torch
@require_vision
@slow
class 			SCREAMING_SNAKE_CASE__ (   unittest.TestCase  ):

       @slow
       def        snake_case__  (				self :			List[str]       ):
           __snake_case    :							Dict             =  GLPNImageProcessor.from_pretrained(GLPN_PRETRAINED_MODEL_ARCHIVE_LIST[0]       )
           __snake_case    :							Dict             =  GLPNForDepthEstimation.from_pretrained(GLPN_PRETRAINED_MODEL_ARCHIVE_LIST[0]       ).to(A_       )

           __snake_case    :							List[str]             =  prepare_img()
           __snake_case    :							int             =  image_processor(images=A_       ,       return_tensors="""pt"""       ).to(A_       )

           # forward pass
           with torch.no_grad():
               __snake_case    :							List[Any]             =  model(**A_       )

           # verify the predicted depth
           __snake_case    :							Optional[Any]             =  torch.Size([1, 4_80, 6_40]       )
           self.assertEqual(outputs.predicted_depth.shape       ,       A_       )

           __snake_case    :							Tuple             =  torch.tensor(
               [[3.4291, 2.7865, 2.5151], [3.2841, 2.7021, 2.3502], [3.1147, 2.4625, 2.2481]]       ).to(A_       )

           self.assertTrue(torch.allclose(outputs.predicted_depth[0, :3, :3]       ,       A_       ,       atol=1e-4       )       )






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()


