"""simple docstring"""







import tempfile
import unittest

import numpy as np

import transformers
from transformers import GPTaConfig, GPTaTokenizer, is_flax_available, is_torch_available
from transformers.testing_utils import is_pt_flax_cross_test, require_flax, slow

from ...generation.test_flax_utils import FlaxGenerationTesterMixin
from ...test_modeling_flax_common import FlaxModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask


if is_flax_available():
     import jax
     import jax.numpy as jnp

     from transformers.modeling_flax_pytorch_utils import (
         convert_pytorch_state_dict_to_flax,
         load_flax_weights_in_pytorch_model,
     )
     from transformers.models.gpta.modeling_flax_gpta import FlaxGPTaLMHeadModel, FlaxGPTaModel

if is_torch_available():
     import torch






class     _SCREAMING_SNAKE_CASE       :



   '''simple docstring'''



   def __init__(  self   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE=14   ,							_SCREAMING_SNAKE_CASE=7   ,							_SCREAMING_SNAKE_CASE=True   ,							_SCREAMING_SNAKE_CASE=True   ,							_SCREAMING_SNAKE_CASE=False   ,							_SCREAMING_SNAKE_CASE=True   ,							_SCREAMING_SNAKE_CASE=99   ,							_SCREAMING_SNAKE_CASE=32   ,							_SCREAMING_SNAKE_CASE=5   ,							_SCREAMING_SNAKE_CASE=4   ,							_SCREAMING_SNAKE_CASE=37   ,							_SCREAMING_SNAKE_CASE="gelu"   ,							_SCREAMING_SNAKE_CASE=0.1   ,							_SCREAMING_SNAKE_CASE=0.1   ,							_SCREAMING_SNAKE_CASE=512   ,							_SCREAMING_SNAKE_CASE=0.02   ,							):


         '''simple docstring'''

         __lowerCamelCase								=				parent
         __lowerCamelCase								=				batch_size
         __lowerCamelCase								=				seq_length
         __lowerCamelCase								=				is_training
         __lowerCamelCase								=				use_input_mask
         __lowerCamelCase								=				use_token_type_ids
         __lowerCamelCase								=				use_labels
         __lowerCamelCase								=				vocab_size
         __lowerCamelCase								=				hidden_size
         __lowerCamelCase								=				num_hidden_layers
         __lowerCamelCase								=				num_attention_heads
         __lowerCamelCase								=				intermediate_size
         __lowerCamelCase								=				hidden_act
         __lowerCamelCase								=				hidden_dropout_prob
         __lowerCamelCase								=				attention_probs_dropout_prob
         __lowerCamelCase								=				max_position_embeddings
         __lowerCamelCase								=				initializer_range
         __lowerCamelCase								=				None
         __lowerCamelCase								=				vocab_size - 1
         __lowerCamelCase								=				vocab_size - 1
         __lowerCamelCase								=				vocab_size - 1







   def       _A							(  self  ):


         '''simple docstring'''

         __lowerCamelCase								=				ids_tensor([self.batch_size, self.seq_length]   ,							self.vocab_size  )

         __lowerCamelCase								=				None
         if self.use_input_mask:
               __lowerCamelCase								=				random_attention_mask([self.batch_size, self.seq_length]  )

         __lowerCamelCase								=				GPTaConfig(
             vocab_size=self.vocab_size   ,							n_embd=self.hidden_size   ,							n_layer=self.num_hidden_layers   ,							n_head=self.num_attention_heads   ,							n_positions=self.max_position_embeddings   ,							use_cache=_SCREAMING_SNAKE_CASE   ,							bos_token_id=self.bos_token_id   ,							eos_token_id=self.eos_token_id   ,							pad_token_id=self.pad_token_id   ,							)

         return (config, input_ids, input_mask)







   def       _A							(  self  ):


         '''simple docstring'''

         __lowerCamelCase								=				self.prepare_config_and_inputs()
         __lowerCamelCase		,__lowerCamelCase		,__lowerCamelCase								=				config_and_inputs
         __lowerCamelCase								=				{'input_ids': input_ids, 'attention_mask': attention_mask}
         return config, inputs_dict







   def       _A							(  self  ):


         '''simple docstring'''

         __lowerCamelCase		,__lowerCamelCase		,__lowerCamelCase								=				self.prepare_config_and_inputs()

         __lowerCamelCase								=				floats_tensor([self.batch_size, self.seq_length, self.hidden_size]  )
         __lowerCamelCase								=				ids_tensor([self.batch_size, self.seq_length]   ,							vocab_size=2  )

         return (
             config,
             input_ids,
             attention_mask,
             encoder_hidden_states,
             encoder_attention_mask,
         )







   def       _A							(  self   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  ):


         '''simple docstring'''

         __lowerCamelCase								=				20
         __lowerCamelCase								=				model_class_name(_SCREAMING_SNAKE_CASE  )

         __lowerCamelCase								=				model.init_cache(input_ids.shape[0]   ,							_SCREAMING_SNAKE_CASE  )
         __lowerCamelCase								=				jnp.ones((input_ids.shape[0], max_decoder_length)   ,							dtype='i4'  )

         __lowerCamelCase								=				jnp.broadcast_to(
             jnp.arange(input_ids.shape[-1] - 1  )[None, :]   ,							(input_ids.shape[0], input_ids.shape[-1] - 1)  )
         __lowerCamelCase								=				model(
             input_ids[:, :-1]   ,							attention_mask=_SCREAMING_SNAKE_CASE   ,							past_key_values=_SCREAMING_SNAKE_CASE   ,							position_ids=_SCREAMING_SNAKE_CASE   ,							)

         __lowerCamelCase								=				jnp.array(input_ids.shape[0] * [[input_ids.shape[-1] - 1]]   ,							dtype='i4'  )
         __lowerCamelCase								=				model(
             input_ids[:, -1:]   ,							attention_mask=_SCREAMING_SNAKE_CASE   ,							past_key_values=outputs_cache.past_key_values   ,							position_ids=_SCREAMING_SNAKE_CASE   ,							)

         __lowerCamelCase								=				model(_SCREAMING_SNAKE_CASE  )

         __lowerCamelCase								=				np.max(np.abs((outputs_cache_next[0][:, -1, :5] - outputs[0][:, -1, :5])  )  )
         self.parent.assertTrue(diff < 1E-3   ,							msg=F'''Max diff is {diff}'''  )







   def       _A							(  self   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  ):


         '''simple docstring'''

         __lowerCamelCase								=				20
         __lowerCamelCase								=				model_class_name(_SCREAMING_SNAKE_CASE  )

         __lowerCamelCase								=				jnp.concatenate(
             [attention_mask, jnp.zeros((attention_mask.shape[0], max_decoder_length - attention_mask.shape[1])  )]   ,							axis=-1   ,							)

         __lowerCamelCase								=				model.init_cache(input_ids.shape[0]   ,							_SCREAMING_SNAKE_CASE  )
         __lowerCamelCase								=				jnp.broadcast_to(
             jnp.arange(input_ids.shape[-1] - 1  )[None, :]   ,							(input_ids.shape[0], input_ids.shape[-1] - 1)  )

         __lowerCamelCase								=				model(
             input_ids[:, :-1]   ,							attention_mask=_SCREAMING_SNAKE_CASE   ,							past_key_values=_SCREAMING_SNAKE_CASE   ,							position_ids=_SCREAMING_SNAKE_CASE   ,							)
         __lowerCamelCase								=				jnp.array(input_ids.shape[0] * [[input_ids.shape[-1] - 1]]   ,							dtype='i4'  )
         __lowerCamelCase								=				model(
             input_ids[:, -1:]   ,							past_key_values=outputs_cache.past_key_values   ,							attention_mask=_SCREAMING_SNAKE_CASE   ,							position_ids=_SCREAMING_SNAKE_CASE   ,							)

         __lowerCamelCase								=				model(_SCREAMING_SNAKE_CASE   ,							attention_mask=_SCREAMING_SNAKE_CASE  )

         __lowerCamelCase								=				np.max(np.abs((outputs_cache_next[0][:, -1, :5] - outputs[0][:, -1, :5])  )  )
         self.parent.assertTrue(diff < 1E-3   ,							msg=F'''Max diff is {diff}'''  )






@require_flax
class     _SCREAMING_SNAKE_CASE       ( UpperCAmelCase						,							UpperCAmelCase						,							unittest.TestCase							):



   '''simple docstring'''



   __UpperCAmelCase  :       List[Any]						=						(FlaxGPTaModel, FlaxGPTaLMHeadModel) if is_flax_available() else ()
   __UpperCAmelCase  :       str						=						(FlaxGPTaLMHeadModel,) if is_flax_available() else ()







   def       _A							(  self  ):


         '''simple docstring'''

         __lowerCamelCase								=				FlaxGPTaModelTester(self  )







   def       _A							(  self  ):


         '''simple docstring'''

         for model_class_name in self.all_model_classes:
               __lowerCamelCase		,__lowerCamelCase		,__lowerCamelCase								=				self.model_tester.prepare_config_and_inputs()
               self.model_tester.check_use_cache_forward(_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  )







   def       _A							(  self  ):


         '''simple docstring'''

         for model_class_name in self.all_model_classes:
               __lowerCamelCase		,__lowerCamelCase		,__lowerCamelCase								=				self.model_tester.prepare_config_and_inputs()
               self.model_tester.check_use_cache_forward_with_attn_mask(
                   _SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  )







   @slow
   def       _A							(  self  ):


         '''simple docstring'''

         __lowerCamelCase								=				GPTaTokenizer.from_pretrained('gpt2'   ,							pad_token='</s>'   ,							padding_side='left'  )
         __lowerCamelCase								=				tokenizer(['Hello this is a long string', 'Hey']   ,							return_tensors='np'   ,							padding=_SCREAMING_SNAKE_CASE   ,							truncation=_SCREAMING_SNAKE_CASE  )

         __lowerCamelCase								=				FlaxGPTaLMHeadModel.from_pretrained('gpt2'  )
         __lowerCamelCase								=				False
         __lowerCamelCase								=				model.config.eos_token_id

         __lowerCamelCase								=				jax.jit(model.generate  )

         __lowerCamelCase								=				jit_generate(inputs['input_ids']   ,							attention_mask=inputs['attention_mask']  ).sequences

         __lowerCamelCase								=				tokenizer.batch_decode(_SCREAMING_SNAKE_CASE   ,							skip_special_tokens=_SCREAMING_SNAKE_CASE  )

         __lowerCamelCase								=				[
             'Hello this is a long string of words. I\'m going to start with the first one.\n',
             'Hey, I\'m not sure if I\'m going to be able to do',
         ]

         self.assertListEqual(_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  )







   @is_pt_flax_cross_test
   def       _A							(  self  ):


         '''simple docstring'''

         __lowerCamelCase		,__lowerCamelCase								=				self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
               with self.subTest(model_class.__name__  ):
                     # prepare inputs
                     __lowerCamelCase								=				self._prepare_for_class(_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  )
                     __lowerCamelCase								=				{k: torch.tensor(v.tolist()  ) for k, v in prepared_inputs_dict.items()}

                     # load corresponding PyTorch class
                     __lowerCamelCase								=				model_class.__name__[4:]  # Skip the "Flax" at the beginning
                     __lowerCamelCase								=				getattr(_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  )

                     __lowerCamelCase		,__lowerCamelCase								=				pt_inputs['input_ids'].shape
                     __lowerCamelCase								=				np.random.randint(0   ,							seq_length - 1   ,							size=(batch_size,)  )
                     for batch_idx, start_index in enumerate(_SCREAMING_SNAKE_CASE  ):
                           __lowerCamelCase								=				0
                           __lowerCamelCase								=				1
                           __lowerCamelCase								=				0
                           __lowerCamelCase								=				1
                     __lowerCamelCase								=				pt_model_class(_SCREAMING_SNAKE_CASE  ).eval()
                     __lowerCamelCase								=				model_class(_SCREAMING_SNAKE_CASE   ,							dtype=jnp.floataa  )

                     __lowerCamelCase								=				convert_pytorch_state_dict_to_flax(pt_model.state_dict()   ,							_SCREAMING_SNAKE_CASE  )
                     __lowerCamelCase								=				fx_state

                     with torch.no_grad():
                           __lowerCamelCase								=				pt_model(**_SCREAMING_SNAKE_CASE  ).to_tuple()

                     __lowerCamelCase								=				fx_model(**_SCREAMING_SNAKE_CASE  ).to_tuple()
                     self.assertEqual(len(_SCREAMING_SNAKE_CASE  )   ,							len(_SCREAMING_SNAKE_CASE  )   ,							'Output lengths differ between Flax and PyTorch'  )
                     for fx_output, pt_output in zip(_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  ):
                           self.assert_almost_equals(fx_output[:, -1]   ,							pt_output[:, -1].numpy()   ,							4E-2  )

                     with tempfile.TemporaryDirectory() as tmpdirname:
                           pt_model.save_pretrained(_SCREAMING_SNAKE_CASE  )
                           __lowerCamelCase								=				model_class.from_pretrained(_SCREAMING_SNAKE_CASE   ,							from_pt=_SCREAMING_SNAKE_CASE  )

                     __lowerCamelCase								=				fx_model_loaded(**_SCREAMING_SNAKE_CASE  ).to_tuple()
                     self.assertEqual(
                         len(_SCREAMING_SNAKE_CASE  )   ,							len(_SCREAMING_SNAKE_CASE  )   ,							'Output lengths differ between Flax and PyTorch'  )
                     for fx_output_loaded, pt_output in zip(_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  ):
                           self.assert_almost_equals(fx_output_loaded[:, -1]   ,							pt_output[:, -1].numpy()   ,							4E-2  )







   @is_pt_flax_cross_test
   def       _A							(  self  ):


         '''simple docstring'''

         __lowerCamelCase		,__lowerCamelCase								=				self.model_tester.prepare_config_and_inputs_for_common()
         for model_class in self.all_model_classes:
               with self.subTest(model_class.__name__  ):
                     # prepare inputs
                     __lowerCamelCase								=				self._prepare_for_class(_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  )
                     __lowerCamelCase								=				{k: torch.tensor(v.tolist()  ) for k, v in prepared_inputs_dict.items()}

                     # load corresponding PyTorch class
                     __lowerCamelCase								=				model_class.__name__[4:]  # Skip the "Flax" at the beginning
                     __lowerCamelCase								=				getattr(_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  )

                     __lowerCamelCase								=				pt_model_class(_SCREAMING_SNAKE_CASE  ).eval()
                     __lowerCamelCase								=				model_class(_SCREAMING_SNAKE_CASE   ,							dtype=jnp.floataa  )

                     __lowerCamelCase								=				load_flax_weights_in_pytorch_model(_SCREAMING_SNAKE_CASE   ,							fx_model.params  )
                     __lowerCamelCase		,__lowerCamelCase								=				pt_inputs['input_ids'].shape
                     __lowerCamelCase								=				np.random.randint(0   ,							seq_length - 1   ,							size=(batch_size,)  )
                     for batch_idx, start_index in enumerate(_SCREAMING_SNAKE_CASE  ):
                           __lowerCamelCase								=				0
                           __lowerCamelCase								=				1
                           __lowerCamelCase								=				0
                           __lowerCamelCase								=				1

                     # make sure weights are tied in PyTorch
                     pt_model.tie_weights()

                     with torch.no_grad():
                           __lowerCamelCase								=				pt_model(**_SCREAMING_SNAKE_CASE  ).to_tuple()

                     __lowerCamelCase								=				fx_model(**_SCREAMING_SNAKE_CASE  ).to_tuple()
                     self.assertEqual(len(_SCREAMING_SNAKE_CASE  )   ,							len(_SCREAMING_SNAKE_CASE  )   ,							'Output lengths differ between Flax and PyTorch'  )
                     for fx_output, pt_output in zip(_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  ):
                           self.assert_almost_equals(fx_output[:, -1]   ,							pt_output[:, -1].numpy()   ,							4E-2  )

                     with tempfile.TemporaryDirectory() as tmpdirname:
                           fx_model.save_pretrained(_SCREAMING_SNAKE_CASE  )
                           __lowerCamelCase								=				pt_model_class.from_pretrained(_SCREAMING_SNAKE_CASE   ,							from_flax=_SCREAMING_SNAKE_CASE  )

                     with torch.no_grad():
                           __lowerCamelCase								=				pt_model_loaded(**_SCREAMING_SNAKE_CASE  ).to_tuple()

                     self.assertEqual(
                         len(_SCREAMING_SNAKE_CASE  )   ,							len(_SCREAMING_SNAKE_CASE  )   ,							'Output lengths differ between Flax and PyTorch'  )
                     for fx_output, pt_output in zip(_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  ):
                           self.assert_almost_equals(fx_output[:, -1]   ,							pt_output[:, -1].numpy()   ,							4E-2  )







   @slow
   def       _A							(  self  ):


         '''simple docstring'''

         for model_class_name in self.all_model_classes:
               __lowerCamelCase								=				model_class_name.from_pretrained('gpt2'   ,							from_pt=_SCREAMING_SNAKE_CASE  )
               __lowerCamelCase								=				model(np.ones((1, 1)  )  )
               self.assertIsNotNone(_SCREAMING_SNAKE_CASE  )







"""simple docstring"""







from __future__ import annotations

from collections.abc import Iterable






class     _SCREAMING_SNAKE_CASE       :



   '''simple docstring'''



   def __init__(  self   ,							_SCREAMING_SNAKE_CASE   ,							_SCREAMING_SNAKE_CASE  ):


      '''simple docstring'''

      __lowerCamelCase		,__lowerCamelCase								=				float(_SCREAMING_SNAKE_CASE  ), float(_SCREAMING_SNAKE_CASE  )







   def __eq__(  self   ,							_SCREAMING_SNAKE_CASE  ):


      '''simple docstring'''

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







   def __ne__(  self   ,							_SCREAMING_SNAKE_CASE  ):


      '''simple docstring'''

      return not self == other







   def __gt__(  self   ,							_SCREAMING_SNAKE_CASE  ):


      '''simple docstring'''

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







   def __lt__(  self   ,							_SCREAMING_SNAKE_CASE  ):


      '''simple docstring'''

      return not self > other







   def __ge__(  self   ,							_SCREAMING_SNAKE_CASE  ):


      '''simple docstring'''

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







   def __le__(  self   ,							_SCREAMING_SNAKE_CASE  ):


      '''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 			A__						(  lowercase_    :  list[Point] | list[list[float]] | Iterable[list[float]]			,   )     ->       list[Point]:
   __lowerCamelCase								=				[]
   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 			A__						(  lowercase_    :  list[Point] | list[list[float]]	)     ->       list[Point]:

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

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

   return _construct_points(lowercase_	)



def 			A__						(  lowercase_    :  Point			,   lowercase_    :  Point			,   lowercase_    :  Point	)     ->       float:
   __lowerCamelCase								=				(a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x)
   return det



def 			A__						(  lowercase_    :  list[Point]	)     ->       list[Point]:
   __lowerCamelCase								=				sorted(_validate_input(lowercase_	)	)
   __lowerCamelCase								=				len(lowercase_	)
   __lowerCamelCase								=				set()

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

               if det_k > 0:
                  __lowerCamelCase								=				True
               elif det_k < 0:
                  __lowerCamelCase								=				True
               else:
                  # point[i], point[j], point[k] all lie on a straight line
                  # if point[k] is to the left of point[i] or it's to the
                  # right of point[j], then point[i], point[j] cannot be
                  # part of the convex hull of A
                  if points[k] < points[i] or points[k] > points[j]:
                     __lowerCamelCase								=				False
                     break

            if points_left_of_ij and points_right_of_ij:
               __lowerCamelCase								=				False
               break

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

   return sorted(lowercase_	)



def 			A__						(  lowercase_    :  list[Point]	)     ->       list[Point]:
   __lowerCamelCase								=				sorted(_validate_input(lowercase_	)	)
   __lowerCamelCase								=				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

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

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

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

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

         if det > 0:
            candidate_points.append(lowercase_	)

            if det > extreme_point_distance:
               __lowerCamelCase								=				det
               __lowerCamelCase								=				p

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



def 			A__						(  lowercase_    :  list[Point]	)     ->       list[Point]:
   __lowerCamelCase								=				sorted(_validate_input(lowercase_	)	)
   __lowerCamelCase								=				len(lowercase_	)

   __lowerCamelCase								=				points[:2]
   for i in range(2			,   lowercase_	):
      __lowerCamelCase								=				_det(convex_hull[1]			,   convex_hull[0]			,   points[i]	)
      if det > 0:
         convex_hull.insert(0			,   points[i]	)
         break
      elif det < 0:
         convex_hull.append(points[i]	)
         break
      else:
         __lowerCamelCase								=				points[i]
   i += 1

   for j in range(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 			A__						(  )     ->       List[Any]:
   __lowerCamelCase								=				[
       (0, 3),
       (2, 2),
       (1, 1),
       (2, 1),
       (3, 0),
       (0, 0),
       (3, 3),
       (2, -1),
       (2, -4),
       (1, -3),
   ]
   # the convex set of points is
   # [(0, 0), (0, 3), (1, -3), (2, -4), (3, 0), (3, 3)]
   __lowerCamelCase								=				convex_hull_bf(lowercase_	)

   __lowerCamelCase								=				convex_hull_recursive(lowercase_	)
   assert results_bf == results_recursive

   __lowerCamelCase								=				convex_hull_melkman(lowercase_	)
   assert results_bf == results_melkman

   print(lowercase_	)


if __name__ == "__main__":
     main()






