
from __future__ import annotations

import inspect
import unittest

from transformers import MobileViTConfig
from transformers.file_utils import is_tf_available, is_vision_available
from transformers.testing_utils import require_tf, slow

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
   import numpy as np
   import tensorflow as tf

   from transformers import TFMobileViTForImageClassification, TFMobileViTForSemanticSegmentation, TFMobileViTModel
   from transformers.models.mobilevit.modeling_tf_mobilevit import TF_MOBILEVIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
   from PIL import Image

   from transformers import MobileViTImageProcessor





class 				UpperCamelCase__		(	__SCREAMING_SNAKE_CASE	):






       """simple docstring"""


       def     _UpperCamelCase	(							self	)				->				List[Any]:
          SCREAMING_SNAKE_CASE_	=      self.config_class(**self.inputs_dict	)
          self.parent.assertTrue(hasattr(_A ,     '''hidden_sizes'''	)	)
          self.parent.assertTrue(hasattr(_A ,     '''neck_hidden_sizes'''	)	)
          self.parent.assertTrue(hasattr(_A ,     '''num_attention_heads'''	)	)







class 				UpperCamelCase__		:






       """simple docstring"""


       def __init__(							self ,     _A ,     _A=13 ,     _A=32 ,     _A=2 ,     _A=3 ,     _A=640 ,     _A=4 ,     _A="silu" ,     _A=3 ,     _A=32 ,     _A=0.1 ,     _A=0.1 ,     _A=0.1 ,     _A=0.02 ,     _A=True ,     _A=True ,     _A=10 ,     _A=None ,     )				->				str:
          SCREAMING_SNAKE_CASE_	=      parent
          SCREAMING_SNAKE_CASE_	=      batch_size
          SCREAMING_SNAKE_CASE_	=      image_size
          SCREAMING_SNAKE_CASE_	=      patch_size
          SCREAMING_SNAKE_CASE_	=      num_channels
          SCREAMING_SNAKE_CASE_	=      last_hidden_size
          SCREAMING_SNAKE_CASE_	=      num_attention_heads
          SCREAMING_SNAKE_CASE_	=      hidden_act
          SCREAMING_SNAKE_CASE_	=      conv_kernel_size
          SCREAMING_SNAKE_CASE_	=      output_stride
          SCREAMING_SNAKE_CASE_	=      hidden_dropout_prob
          SCREAMING_SNAKE_CASE_	=      attention_probs_dropout_prob
          SCREAMING_SNAKE_CASE_	=      classifier_dropout_prob
          SCREAMING_SNAKE_CASE_	=      use_labels
          SCREAMING_SNAKE_CASE_	=      is_training
          SCREAMING_SNAKE_CASE_	=      num_labels
          SCREAMING_SNAKE_CASE_	=      initializer_range
          SCREAMING_SNAKE_CASE_	=      scope



       def     _UpperCamelCase	(							self	)				->				Tuple:
          SCREAMING_SNAKE_CASE_	=      floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]	)

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

          SCREAMING_SNAKE_CASE_	=      self.get_config()

          return config, pixel_values, labels, pixel_labels



       def     _UpperCamelCase	(							self	)				->				Any:
          return MobileViTConfig(
              image_size=self.image_size ,     patch_size=self.patch_size ,     num_channels=self.num_channels ,     num_attention_heads=self.num_attention_heads ,     hidden_act=self.hidden_act ,     conv_kernel_size=self.conv_kernel_size ,     output_stride=self.output_stride ,     hidden_dropout_prob=self.hidden_dropout_prob ,     attention_probs_dropout_prob=self.attention_probs_dropout_prob ,     classifier_dropout_prob=self.classifier_dropout_prob ,     initializer_range=self.initializer_range ,     )



       def     _UpperCamelCase	(							self ,     _A ,     _A ,     _A ,     _A	)				->				Tuple:
          SCREAMING_SNAKE_CASE_	=      TFMobileViTModel(config=_A	)
          SCREAMING_SNAKE_CASE_	=      model(_A ,     training=_A	)
          SCREAMING_SNAKE_CASE_	=      SCREAMING_SNAKE_CASE_	=      self.image_size // self.output_stride
          self.parent.assertEqual(
              result.last_hidden_state.shape ,     (self.batch_size, self.last_hidden_size, expected_height, expected_width)	)



       def     _UpperCamelCase	(							self ,     _A ,     _A ,     _A ,     _A	)				->				Dict:
          SCREAMING_SNAKE_CASE_	=      self.num_labels
          SCREAMING_SNAKE_CASE_	=      TFMobileViTForImageClassification(_A	)
          SCREAMING_SNAKE_CASE_	=      model(_A ,     labels=_A ,     training=_A	)
          self.parent.assertEqual(result.logits.shape ,     (self.batch_size, self.num_labels)	)



       def     _UpperCamelCase	(							self ,     _A ,     _A ,     _A ,     _A	)				->				List[str]:
          SCREAMING_SNAKE_CASE_	=      self.num_labels
          SCREAMING_SNAKE_CASE_	=      TFMobileViTForSemanticSegmentation(_A	)
          SCREAMING_SNAKE_CASE_	=      SCREAMING_SNAKE_CASE_	=      self.image_size // self.output_stride

          SCREAMING_SNAKE_CASE_	=      model(_A ,     training=_A	)
          self.parent.assertEqual(
              result.logits.shape ,     (self.batch_size, self.num_labels, expected_height, expected_width)	)

          SCREAMING_SNAKE_CASE_	=      model(_A ,     labels=_A ,     training=_A	)
          self.parent.assertEqual(
              result.logits.shape ,     (self.batch_size, self.num_labels, expected_height, expected_width)	)




       def     _UpperCamelCase	(							self	)				->				Optional[Any]:
          SCREAMING_SNAKE_CASE_	=      self.prepare_config_and_inputs()
          SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	=      config_and_inputs
          SCREAMING_SNAKE_CASE_	=      {'''pixel_values''': pixel_values}
          return config, inputs_dict







@require_tf
class 				UpperCamelCase__		(	__SCREAMING_SNAKE_CASE       ,    __SCREAMING_SNAKE_CASE       ,    unittest.TestCase	):






       """simple docstring"""


       UpperCAmelCase_				       =(
           (TFMobileViTModel, TFMobileViTForImageClassification, TFMobileViTForSemanticSegmentation)
           if is_tf_available()
           else ()
       )
       UpperCAmelCase_				       =(
           {"feature-extraction": TFMobileViTModel, "image-classification": TFMobileViTForImageClassification}
           if is_tf_available()
           else {}
       )

       UpperCAmelCase_				       =False
       UpperCAmelCase_				       =False
       UpperCAmelCase_				       =False
       UpperCAmelCase_				       =False
       UpperCAmelCase_				       =False



       def     _UpperCamelCase	(							self	)				->				Tuple:
          SCREAMING_SNAKE_CASE_	=      TFMobileViTModelTester(self	)
          SCREAMING_SNAKE_CASE_	=      TFMobileViTConfigTester(self ,     config_class=_A ,     has_text_modality=_A	)



       def     _UpperCamelCase	(							self	)				->				str:
          self.config_tester.run_common_tests()



       @unittest.skip(reason='''MobileViT does not use inputs_embeds'''	)
       def     _UpperCamelCase	(							self	)				->				List[str]:
          pass



       @unittest.skip(reason='''MobileViT does not support input and output embeddings'''	)
       def     _UpperCamelCase	(							self	)				->				Union[str, Any]:
          pass



       @unittest.skip(reason='''MobileViT does not output attentions'''	)
       def     _UpperCamelCase	(							self	)				->				Optional[Any]:
          pass



       def     _UpperCamelCase	(							self	)				->				Union[str, Any]:
          SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	=      self.model_tester.prepare_config_and_inputs_for_common()

          for model_class in self.all_model_classes:
             SCREAMING_SNAKE_CASE_	=      model_class(_A	)
             SCREAMING_SNAKE_CASE_	=      inspect.signature(model.call	)
             # signature.parameters is an OrderedDict => so arg_names order is deterministic
             SCREAMING_SNAKE_CASE_	=      [*signature.parameters.keys()]

             SCREAMING_SNAKE_CASE_	=      ['''pixel_values''']
             self.assertListEqual(arg_names[:1] ,     _A	)



       def     _UpperCamelCase	(							self	)				->				Optional[int]:
          SCREAMING_SNAKE_CASE_	=      self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_model(*_A	)



       def     _UpperCamelCase	(							self	)				->				Optional[int]:
          def check_hidden_states_output(_A ,     _A ,     _A	):
             SCREAMING_SNAKE_CASE_	=      model_class(_A	)

             SCREAMING_SNAKE_CASE_	=      model(**self._prepare_for_class(_A ,     _A	)	)

             SCREAMING_SNAKE_CASE_	=      outputs.hidden_states

             SCREAMING_SNAKE_CASE_	=      5
             self.assertEqual(len(_A	) ,     _A	)

             # MobileViT's feature maps are of shape (batch_size, num_channels, height, width)
             # with the width and height being successively divided by 2.
             SCREAMING_SNAKE_CASE_	=      2
             for i in range(len(_A	)	):
                self.assertListEqual(
                    list(hidden_states[i].shape[-2:]	) ,     [self.model_tester.image_size // divisor, self.model_tester.image_size // divisor] ,     )
                divisor *= 2

             self.assertEqual(self.model_tester.output_stride ,     divisor // 2	)

          SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	=      self.model_tester.prepare_config_and_inputs_for_common()

          for model_class in self.all_model_classes:
             SCREAMING_SNAKE_CASE_	=      True
             check_hidden_states_output(_A ,     _A ,     _A	)

             # check that output_hidden_states also work using config
             del inputs_dict["output_hidden_states"]
             SCREAMING_SNAKE_CASE_	=      True

             check_hidden_states_output(_A ,     _A ,     _A	)



       def     _UpperCamelCase	(							self	)				->				List[Any]:
          SCREAMING_SNAKE_CASE_	=      self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_for_image_classification(*_A	)



       def     _UpperCamelCase	(							self	)				->				List[str]:
          SCREAMING_SNAKE_CASE_	=      self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_for_semantic_segmentation(*_A	)



       @unittest.skipIf(
           not is_tf_available() or len(tf.config.list_physical_devices('''GPU'''	)	) == 0 ,     reason='''TF does not support backprop for grouped convolutions on CPU.''' ,     )
       def     _UpperCamelCase	(							self	)				->				List[str]:
          super().test_dataset_conversion()



       def     _UpperCamelCase	(							self ,     _A ,     _A ,     _A=2E-1 ,     _A=2E-1	)				->				Optional[Any]:
          self.assertTrue(np.allclose(_A ,     _A ,     atol=_A ,     rtol=_A	)	)



       @unittest.skipIf(
           not is_tf_available() or len(tf.config.list_physical_devices('''GPU'''	)	) == 0 ,     reason='''TF does not support backprop for grouped convolutions on CPU.''' ,     )
       @slow
       def     _UpperCamelCase	(							self	)				->				List[str]:
          SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	=      self.model_tester.prepare_config_and_inputs_for_common()

          for model_class in self.all_model_classes:
             # Since `TFMobileViTModel` cannot operate with the default `fit()` method.
             if model_class.__name__ != "TFMobileViTModel":
                SCREAMING_SNAKE_CASE_	=      model_class(_A	)
                if getattr(_A ,     '''hf_compute_loss''' ,     _A	):
                   super().test_keras_fit()



       def     _UpperCamelCase	(							self	)				->				int:
          SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	=      self.model_tester.prepare_config_and_inputs_for_common()
          for model_class in self.all_model_classes:
             # set an ignore index to correctly test the masked loss used in
             # `TFMobileViTForSemanticSegmentation`.
             if model_class.__name__ != "TFMobileViTForSemanticSegmentation":
                SCREAMING_SNAKE_CASE_	=      5

             SCREAMING_SNAKE_CASE_	=      model_class(_A	)
             if getattr(_A ,     '''hf_compute_loss''' ,     _A	):
                # The number of elements in the loss should be the same as the number of elements in the label
                SCREAMING_SNAKE_CASE_	=      self._prepare_for_class(inputs_dict.copy() ,     _A ,     return_labels=_A	)
                SCREAMING_SNAKE_CASE_	=      prepared_for_class[
                    sorted(prepared_for_class.keys() - inputs_dict.keys() ,     reverse=_A	)[0]
                ]
                SCREAMING_SNAKE_CASE_	=      added_label.shape.as_list()[:1]

                # Test that model correctly compute the loss with kwargs
                SCREAMING_SNAKE_CASE_	=      self._prepare_for_class(inputs_dict.copy() ,     _A ,     return_labels=_A	)
                SCREAMING_SNAKE_CASE_	=      {'''input_ids''', '''pixel_values''', '''input_features'''}
                SCREAMING_SNAKE_CASE_	=      possible_input_names.intersection(set(_A	)	).pop()
                SCREAMING_SNAKE_CASE_	=      prepared_for_class.pop(_A	)

                SCREAMING_SNAKE_CASE_	=      model(_A ,     **_A	)[0]
                self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1]	)

                # Test that model correctly compute the loss when we mask some positions
                SCREAMING_SNAKE_CASE_	=      self._prepare_for_class(inputs_dict.copy() ,     _A ,     return_labels=_A	)
                SCREAMING_SNAKE_CASE_	=      {'''input_ids''', '''pixel_values''', '''input_features'''}
                SCREAMING_SNAKE_CASE_	=      possible_input_names.intersection(set(_A	)	).pop()
                SCREAMING_SNAKE_CASE_	=      prepared_for_class.pop(_A	)
                if "labels" in prepared_for_class:
                   SCREAMING_SNAKE_CASE_	=      prepared_for_class['''labels'''].numpy()
                   if len(labels.shape	) > 1 and labels.shape[1] != 1:
                      # labels[0] = -100
                      SCREAMING_SNAKE_CASE_	=      tf.convert_to_tensor(_A	)
                      SCREAMING_SNAKE_CASE_	=      model(_A ,     **_A	)[0]
                      self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1]	)
                      self.assertTrue(not np.any(np.isnan(loss.numpy()	)	)	)

                # Test that model correctly compute the loss with a dict
                SCREAMING_SNAKE_CASE_	=      self._prepare_for_class(inputs_dict.copy() ,     _A ,     return_labels=_A	)
                SCREAMING_SNAKE_CASE_	=      model(_A	)[0]
                self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1]	)

                # Test that model correctly compute the loss with a tuple
                SCREAMING_SNAKE_CASE_	=      self._prepare_for_class(inputs_dict.copy() ,     _A ,     return_labels=_A	)

                # Get keys that were added with the _prepare_for_class function
                SCREAMING_SNAKE_CASE_	=      prepared_for_class.keys() - inputs_dict.keys()
                SCREAMING_SNAKE_CASE_	=      inspect.signature(model.call	).parameters
                SCREAMING_SNAKE_CASE_	=      list(signature.keys()	)

                # Create a dictionary holding the location of the tensors in the tuple
                SCREAMING_SNAKE_CASE_	=      {0: input_name}
                for label_key in label_keys:
                   SCREAMING_SNAKE_CASE_	=      signature_names.index(_A	)
                   SCREAMING_SNAKE_CASE_	=      label_key
                SCREAMING_SNAKE_CASE_	=      sorted(tuple_index_mapping.items()	)
                # Initialize a list with their default values, update the values and convert to a tuple
                SCREAMING_SNAKE_CASE_	=      []

                for name in signature_names:
                   if name != "kwargs":
                      list_input.append(signature[name].default	)

                for index, value in sorted_tuple_index_mapping:
                   SCREAMING_SNAKE_CASE_	=      prepared_for_class[value]

                SCREAMING_SNAKE_CASE_	=      tuple(_A	)

                # Send to model
                SCREAMING_SNAKE_CASE_	=      model(tuple_input[:-1]	)[0]

                self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1]	)




       @slow
       def     _UpperCamelCase	(							self	)				->				Any:
          for model_name in TF_MOBILEVIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
             SCREAMING_SNAKE_CASE_	=      TFMobileViTModel.from_pretrained(_A	)
             self.assertIsNotNone(_A	)







def  A__ (       ):
   SCREAMING_SNAKE_CASE_	=      Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''						)
   return image





@require_tf
class 				UpperCamelCase__		(	unittest.TestCase	):






       """simple docstring"""


       @slow
       def     _UpperCamelCase	(							self	)				->				Union[str, Any]:
          SCREAMING_SNAKE_CASE_	=      TFMobileViTForImageClassification.from_pretrained('''apple/mobilevit-xx-small'''	)

          SCREAMING_SNAKE_CASE_	=      MobileViTImageProcessor.from_pretrained('''apple/mobilevit-xx-small'''	)
          SCREAMING_SNAKE_CASE_	=      prepare_img()
          SCREAMING_SNAKE_CASE_	=      image_processor(images=_A ,     return_tensors='''tf'''	)

          # forward pass
          SCREAMING_SNAKE_CASE_	=      model(**_A ,     training=_A	)

          # verify the logits
          SCREAMING_SNAKE_CASE_	=      tf.TensorShape((1, 1000)	)
          self.assertEqual(outputs.logits.shape ,     _A	)

          SCREAMING_SNAKE_CASE_	=      tf.constant([-1.9364, -1.2327, -0.4653]	)

          tf.debugging.assert_near(outputs.logits[0, :3] ,     _A ,     atol=1E-4 ,     rtol=1E-04	)




       @slow
       def     _UpperCamelCase	(							self	)				->				int:
          # `from_pt` will be removed
          SCREAMING_SNAKE_CASE_	=      TFMobileViTForSemanticSegmentation.from_pretrained('''apple/deeplabv3-mobilevit-xx-small'''	)

          SCREAMING_SNAKE_CASE_	=      MobileViTImageProcessor.from_pretrained('''apple/deeplabv3-mobilevit-xx-small'''	)

          SCREAMING_SNAKE_CASE_	=      prepare_img()
          SCREAMING_SNAKE_CASE_	=      image_processor(images=_A ,     return_tensors='''tf'''	)

          # forward pass
          SCREAMING_SNAKE_CASE_	=      model(inputs.pixel_values ,     training=_A	)
          SCREAMING_SNAKE_CASE_	=      outputs.logits

          # verify the logits
          SCREAMING_SNAKE_CASE_	=      tf.TensorShape((1, 21, 32, 32)	)
          self.assertEqual(logits.shape ,     _A	)

          SCREAMING_SNAKE_CASE_	=      tf.constant(
              [
                  [[6.9713, 6.9786, 7.2422], [7.2893, 7.2825, 7.4446], [7.6580, 7.8797, 7.9420]],
                  [[-10.6869, -10.3250, -10.3471], [-10.4228, -9.9868, -9.7132], [-11.0405, -11.0221, -10.7318]],
                  [[-3.3089, -2.8539, -2.6740], [-3.2706, -2.5621, -2.5108], [-3.2534, -2.6615, -2.6651]],
              ]	)

          tf.debugging.assert_near(logits[0, :3, :3, :3] ,     _A ,     rtol=1E-4 ,     atol=1E-4	)




from __future__ import annotations

from collections.abc import Iterable





class 				UpperCamelCase__		:






       """simple docstring"""


       def __init__(							self ,     _A ,     _A	)				->				Union[str, Any]:
          SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	=      float(_A	), float(_A	)



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



       def __ne__(							self ,     _A	)				->				Any:
          return not self == other



       def __gt__(							self ,     _A	)				->				List[Any]:
          if self.x > other.x:
             return True
          elif self.x == other.x:
             return self.y > other.y
          return False



       def __lt__(							self ,     _A	)				->				Optional[int]:
          return not self > other



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



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



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




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







def  A__ (       __lowerCamelCase,  ):
   SCREAMING_SNAKE_CASE_	=      []
   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  A__ (       __lowerCamelCase						):

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

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

   return _construct_points(__lowerCamelCase						)


def  A__ (       __lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase						):
   SCREAMING_SNAKE_CASE_	=      (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x)
   return det


def  A__ (       __lowerCamelCase						):
   SCREAMING_SNAKE_CASE_	=      sorted(_validate_input(__lowerCamelCase						)						)
   SCREAMING_SNAKE_CASE_	=      len(__lowerCamelCase						)
   SCREAMING_SNAKE_CASE_	=      set()

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

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

            if points_left_of_ij and points_right_of_ij:
               SCREAMING_SNAKE_CASE_	=      False
               break

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

   return sorted(__lowerCamelCase						)


def  A__ (       __lowerCamelCase						):
   SCREAMING_SNAKE_CASE_	=      sorted(_validate_input(__lowerCamelCase						)						)
   SCREAMING_SNAKE_CASE_	=      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

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

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

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

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

         if det > 0:
            candidate_points.append(__lowerCamelCase						)

            if det > extreme_point_distance:
               SCREAMING_SNAKE_CASE_	=      det
               SCREAMING_SNAKE_CASE_	=      p

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


def  A__ (       __lowerCamelCase						):
   SCREAMING_SNAKE_CASE_	=      sorted(_validate_input(__lowerCamelCase						)						)
   SCREAMING_SNAKE_CASE_	=      len(__lowerCamelCase						)

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

   SCREAMING_SNAKE_CASE_	=      convex_hull_recursive(__lowerCamelCase						)
   assert results_bf == results_recursive

   SCREAMING_SNAKE_CASE_	=      convex_hull_melkman(__lowerCamelCase						)
   assert results_bf == results_melkman

   print(__lowerCamelCase						)


if __name__ == "__main__":
   main()


