



'''simple docstring'''





import argparse
import logging
import os
from pathlib import Path
from typing import Any, Dict

import pytorch_lightning as pl
from pytorch_lightning.utilities import rank_zero_info

from transformers import (
    AdamW,
    AutoConfig,
    AutoModel,
    AutoModelForPreTraining,
    AutoModelForQuestionAnswering,
    AutoModelForSeqaSeqLM,
    AutoModelForSequenceClassification,
    AutoModelForTokenClassification,
    AutoModelWithLMHead,
    AutoTokenizer,
    PretrainedConfig,
    PreTrainedTokenizer,
)
from transformers.optimization import (
    Adafactor,
    get_cosine_schedule_with_warmup,
    get_cosine_with_hard_restarts_schedule_with_warmup,
    get_linear_schedule_with_warmup,
    get_polynomial_decay_schedule_with_warmup,
)
from transformers.utils.versions import require_version


_UpperCamelCase							    =						logging.getLogger(__name__)

require_version('pytorch_lightning>=1.0.4')

_UpperCamelCase							    =						{
    '''base''': AutoModel,
    '''sequence-classification''': AutoModelForSequenceClassification,
    '''question-answering''': AutoModelForQuestionAnswering,
    '''pretraining''': AutoModelForPreTraining,
    '''token-classification''': AutoModelForTokenClassification,
    '''language-modeling''': AutoModelWithLMHead,
    '''summarization''': AutoModelForSeqaSeqLM,
    '''translation''': AutoModelForSeqaSeqLM,
}


# update this and the import above to support new schedulers from transformers.optimization
_UpperCamelCase							    =						{
    '''linear''': get_linear_schedule_with_warmup,
    '''cosine''': get_cosine_schedule_with_warmup,
    '''cosine_w_restarts''': get_cosine_with_hard_restarts_schedule_with_warmup,
    '''polynomial''': get_polynomial_decay_schedule_with_warmup,
    # '': get_constant_schedule,             # not supported for now
    # '': get_constant_schedule_with_warmup, # not supported for now
}
_UpperCamelCase							    =						sorted(arg_to_scheduler.keys())
_UpperCamelCase							    =						'''{''' + ''', '''.join(arg_to_scheduler_choices) + '''}'''






class  lowerCamelCase_   (    pl.LightningModule					):
  """simple docstring"""




  def __init__(			self				:     Optional[Any]      ,     _a				:     List[str]      ,     _a				:     Dict=None      ,     _a				:     Any="base"      ,     _a				:     Dict=None      ,     _a				:     Any=None      ,     _a				:     Optional[Any]=None      ,     **_a				:     Any      ,     ) -> Dict:
    super().__init__()
    # TODO: move to self.save_hyperparameters()
    # self.save_hyperparameters()
    # can also expand arguments into trainer signature for easier reading

    self.save_hyperparameters(__SCREAMING_SNAKE_CASE       )
    __lowerCamelCase	:	Union[str, Any]   	=			0
    __lowerCamelCase	:	Dict   	=			Path(self.hparams.output_dir       )
    __lowerCamelCase	:	List[str]   	=			self.hparams.cache_dir if self.hparams.cache_dir else None
    if config is None:
      __lowerCamelCase	:	Dict   	=			AutoConfig.from_pretrained(
          self.hparams.config_name if self.hparams.config_name else self.hparams.model_name_or_path      ,     **({'num_labels': num_labels} if num_labels is not None else {})      ,     cache_dir=__SCREAMING_SNAKE_CASE      ,     **__SCREAMING_SNAKE_CASE      ,     )
    else:
      __lowerCamelCase	:	int   	=			config

    __lowerCamelCase	:	List[str]   	=			('encoder_layerdrop', 'decoder_layerdrop', 'dropout', 'attention_dropout')
    for p in extra_model_params:
      if getattr(self.hparams      ,     __SCREAMING_SNAKE_CASE      ,     __SCREAMING_SNAKE_CASE       ):
        assert hasattr(self.config      ,     __SCREAMING_SNAKE_CASE       ), f'model config doesn\'t have a `{p}` attribute'
        setattr(self.config      ,     __SCREAMING_SNAKE_CASE      ,     getattr(self.hparams      ,     __SCREAMING_SNAKE_CASE       )       )

    if tokenizer is None:
      __lowerCamelCase	:	Union[str, Any]   	=			AutoTokenizer.from_pretrained(
          self.hparams.tokenizer_name if self.hparams.tokenizer_name else self.hparams.model_name_or_path      ,     cache_dir=__SCREAMING_SNAKE_CASE      ,     )
    else:
      __lowerCamelCase	:	Union[str, Any]   	=			tokenizer
    __lowerCamelCase	:	List[Any]   	=			MODEL_MODES[mode]
    if model is None:
      __lowerCamelCase	:	Optional[int]   	=			self.model_type.from_pretrained(
          self.hparams.model_name_or_path      ,     from_tf=bool('.ckpt' in self.hparams.model_name_or_path       )      ,     config=self.config      ,     cache_dir=__SCREAMING_SNAKE_CASE      ,     )
    else:
      __lowerCamelCase	:	str   	=			model




  def 						_lowercase					(			self				:     Tuple      ,     *_a				:     int      ,     **_a				:     Tuple       ) -> Any:
    __lowerCamelCase	:	Union[str, Any]   	=			self.model_type.from_pretrained(*__SCREAMING_SNAKE_CASE      ,     **__SCREAMING_SNAKE_CASE       )




  def 						_lowercase					(			self				:     Dict       ) -> List[Any]:
    __lowerCamelCase	:	int   	=			arg_to_scheduler[self.hparams.lr_scheduler]
    __lowerCamelCase	:	Optional[int]   	=			get_schedule_func(
        self.opt      ,     num_warmup_steps=self.hparams.warmup_steps      ,     num_training_steps=self.total_steps()       )
    __lowerCamelCase	:	int   	=			{'scheduler': scheduler, 'interval': 'step', 'frequency': 1}
    return scheduler




  def 						_lowercase					(			self				:     Any       ) -> int:
    __lowerCamelCase	:	str   	=			self.model
    __lowerCamelCase	:	Any   	=			['bias', 'LayerNorm.weight']
    __lowerCamelCase	:	Optional[Any]   	=			[
        {
            'params': [p for n, p in model.named_parameters() if not any(nd in n for nd in no_decay       )],
            'weight_decay': self.hparams.weight_decay,
        },
        {
            'params': [p for n, p in model.named_parameters() if any(nd in n for nd in no_decay       )],
            'weight_decay': 0.0,
        },
    ]
    if self.hparams.adafactor:
      __lowerCamelCase	:	Tuple   	=			Adafactor(
          __SCREAMING_SNAKE_CASE      ,     lr=self.hparams.learning_rate      ,     scale_parameter=__SCREAMING_SNAKE_CASE      ,     relative_step=__SCREAMING_SNAKE_CASE       )

    else:
      __lowerCamelCase	:	Tuple   	=			AdamW(
          __SCREAMING_SNAKE_CASE      ,     lr=self.hparams.learning_rate      ,     eps=self.hparams.adam_epsilon       )
    __lowerCamelCase	:	List[str]   	=			optimizer

    __lowerCamelCase	:	List[str]   	=			self.get_lr_scheduler()

    return [optimizer], [scheduler]




  def 						_lowercase					(			self				:     Union[str, Any]      ,     _a				:     Union[str, Any]      ,     _a				:     Dict       ) -> int:
    return self.validation_step(__SCREAMING_SNAKE_CASE      ,     __SCREAMING_SNAKE_CASE       )




  def 						_lowercase					(			self				:     str      ,     _a				:     List[Any]       ) -> List[Any]:
    return self.validation_end(__SCREAMING_SNAKE_CASE       )




  def 						_lowercase					(			self				:     Optional[int]       ) -> int:
    __lowerCamelCase	:	Dict   	=			max(1      ,     self.hparams.gpus       )  # TODO: consider num_tpu_cores
    __lowerCamelCase	:	str   	=			self.hparams.train_batch_size * self.hparams.accumulate_grad_batches * num_devices
    return (self.dataset_size / effective_batch_size) * self.hparams.max_epochs




  def 						_lowercase					(			self				:     int      ,     _a				:     Dict       ) -> Optional[int]:
    if mode == "test":
      __lowerCamelCase	:	Tuple   	=			len(self.test_dataloader().dataset       )
    else:
      __lowerCamelCase	:	Optional[Any]   	=			self.get_dataloader('train'      ,     self.hparams.train_batch_size      ,     shuffle=__SCREAMING_SNAKE_CASE       )
      __lowerCamelCase	:	Optional[Any]   	=			len(self.train_dataloader().dataset       )




  def 						_lowercase					(			self				:     int      ,     _a				:     Tuple      ,     _a				:     str      ,     _a				:     Optional[int] = False       ) -> Optional[Any]:
    raise NotImplementedError('You must implement this for your task'       )




  def 						_lowercase					(			self				:     Optional[Any]       ) -> Any:
    return self.train_loader




  def 						_lowercase					(			self				:     Optional[Any]       ) -> Optional[Any]:
    return self.get_dataloader('dev'      ,     self.hparams.eval_batch_size      ,     shuffle=__SCREAMING_SNAKE_CASE       )




  def 						_lowercase					(			self				:     Union[str, Any]       ) -> Optional[int]:
    return self.get_dataloader('test'      ,     self.hparams.eval_batch_size      ,     shuffle=__SCREAMING_SNAKE_CASE       )




  def 						_lowercase					(			self				:     List[Any]      ,     _a				:     List[Any]       ) -> Optional[int]:
    return os.path.join(
        self.hparams.data_dir      ,     'cached_{}_{}_{}'.format(
            __SCREAMING_SNAKE_CASE      ,     list(filter(__SCREAMING_SNAKE_CASE      ,     self.hparams.model_name_or_path.split('/'       )       )       ).pop()      ,     str(self.hparams.max_seq_length       )      ,     )      ,     )




  @pl.utilities.rank_zero_only
  def 						_lowercase					(			self				:     List[str]      ,     _a				:     Optional[Any]       ) -> None:
    __lowerCamelCase	:	Dict   	=			self.output_dir.joinpath('best_tfmr'       )
    __lowerCamelCase	:	Union[str, Any]   	=			self.step_count
    self.model.save_pretrained(__SCREAMING_SNAKE_CASE       )
    self.tokenizer.save_pretrained(__SCREAMING_SNAKE_CASE       )




  @staticmethod
  def 						_lowercase					(			_a				:     Tuple      ,     _a				:     Any       ) -> Optional[int]:
    parser.add_argument(
        '--model_name_or_path'      ,     default=__SCREAMING_SNAKE_CASE      ,     type=__SCREAMING_SNAKE_CASE      ,     required=__SCREAMING_SNAKE_CASE      ,     help='Path to pretrained model or model identifier from huggingface.co/models'      ,     )
    parser.add_argument(
        '--config_name'      ,     default=''      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Pretrained config name or path if not the same as model_name'       )
    parser.add_argument(
        '--tokenizer_name'      ,     default=__SCREAMING_SNAKE_CASE      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Pretrained tokenizer name or path if not the same as model_name'      ,     )
    parser.add_argument(
        '--cache_dir'      ,     default=''      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Where do you want to store the pre-trained models downloaded from huggingface.co'      ,     )
    parser.add_argument(
        '--encoder_layerdrop'      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Encoder layer dropout probability (Optional). Goes into model.config'      ,     )
    parser.add_argument(
        '--decoder_layerdrop'      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Decoder layer dropout probability (Optional). Goes into model.config'      ,     )
    parser.add_argument(
        '--dropout'      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Dropout probability (Optional). Goes into model.config'      ,     )
    parser.add_argument(
        '--attention_dropout'      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Attention dropout probability (Optional). Goes into model.config'      ,     )
    parser.add_argument('--learning_rate'      ,     default=5e-5      ,     type=__SCREAMING_SNAKE_CASE      ,     help='The initial learning rate for Adam.'       )
    parser.add_argument(
        '--lr_scheduler'      ,     default='linear'      ,     choices=__SCREAMING_SNAKE_CASE      ,     metavar=__SCREAMING_SNAKE_CASE      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Learning rate scheduler'      ,     )
    parser.add_argument('--weight_decay'      ,     default=0.0      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Weight decay if we apply some.'       )
    parser.add_argument('--adam_epsilon'      ,     default=1e-8      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Epsilon for Adam optimizer.'       )
    parser.add_argument('--warmup_steps'      ,     default=0      ,     type=__SCREAMING_SNAKE_CASE      ,     help='Linear warmup over warmup_steps.'       )
    parser.add_argument('--num_workers'      ,     default=4      ,     type=__SCREAMING_SNAKE_CASE      ,     help='kwarg passed to DataLoader'       )
    parser.add_argument('--num_train_epochs'      ,     dest='max_epochs'      ,     default=3      ,     type=__SCREAMING_SNAKE_CASE       )
    parser.add_argument('--train_batch_size'      ,     default=32      ,     type=__SCREAMING_SNAKE_CASE       )
    parser.add_argument('--eval_batch_size'      ,     default=32      ,     type=__SCREAMING_SNAKE_CASE       )
    parser.add_argument('--adafactor'      ,     action='store_true'       )






class  lowerCamelCase_   (    pl.Callback					):
  """simple docstring"""




  def 						_lowercase					(			self				:     Optional[int]      ,     _a				:     Optional[int]      ,     _a				:     List[str]       ) -> Any:
    __lowerCamelCase	:	Union[str, Any]   	=			trainer.lr_schedulers[0]['scheduler']
    __lowerCamelCase	:	Tuple   	=			{f'lr_group_{i}': lr for i, lr in enumerate(lr_scheduler.get_lr()       )}
    pl_module.logger.log_metrics(__SCREAMING_SNAKE_CASE       )




  def 						_lowercase					(			self				:     int      ,     _a				:     List[str]      ,     _a				:     int       ) -> List[Any]:
    rank_zero_info('***** Validation results *****'       )
    __lowerCamelCase	:	str   	=			trainer.callback_metrics
    # Log results
    for key in sorted(__SCREAMING_SNAKE_CASE       ):
      if key not in ["log", "progress_bar"]:
        rank_zero_info('{} = {}\n'.format(__SCREAMING_SNAKE_CASE      ,     str(metrics[key]       )       )       )




  def 						_lowercase					(			self				:     str      ,     _a				:     List[str]      ,     _a				:     List[Any]       ) -> Optional[int]:
    rank_zero_info('***** Test results *****'       )
    __lowerCamelCase	:	Optional[int]   	=			trainer.callback_metrics
    # Log and save results to file
    __lowerCamelCase	:	Tuple   	=			os.path.join(pl_module.hparams.output_dir      ,     'test_results.txt'       )
    with open(__SCREAMING_SNAKE_CASE      ,     'w'       ) as writer:
      for key in sorted(__SCREAMING_SNAKE_CASE       ):
        if key not in ["log", "progress_bar"]:
          rank_zero_info('{} = {}\n'.format(__SCREAMING_SNAKE_CASE      ,     str(metrics[key]       )       )       )
          writer.write('{} = {}\n'.format(__SCREAMING_SNAKE_CASE      ,     str(metrics[key]       )       )       )




def 	a_					(							_lowerCAmelCase	,_lowerCAmelCase	)				->				None:
  #  To allow all pl args uncomment the following line
  #  parser = pl.Trainer.add_argparse_args(parser)
  parser.add_argument(
      '--output_dir'	,default=snake_case__	,type=snake_case__	,required=snake_case__	,help='The output directory where the model predictions and checkpoints will be written.'	,)
  parser.add_argument(
      '--fp16'	,action='store_true'	,help='Whether to use 16-bit (mixed) precision (through NVIDIA apex) instead of 32-bit'	,)

  parser.add_argument(
      '--fp16_opt_level'	,type=snake_case__	,default='O2'	,help=(
          'For fp16: Apex AMP optimization level selected in [\'O0\', \'O1\', \'O2\', and \'O3\'].'
          'See details at https://nvidia.github.io/apex/amp.html'
      )	,)
  parser.add_argument('--n_tpu_cores'	,dest='tpu_cores'	,type=snake_case__	)
  parser.add_argument('--max_grad_norm'	,dest='gradient_clip_val'	,default=1.0	,type=snake_case__	,help='Max gradient norm'	)
  parser.add_argument('--do_train'	,action='store_true'	,help='Whether to run training.'	)
  parser.add_argument('--do_predict'	,action='store_true'	,help='Whether to run predictions on the test set.'	)
  parser.add_argument(
      '--gradient_accumulation_steps'	,dest='accumulate_grad_batches'	,type=snake_case__	,default=1	,help='Number of updates steps to accumulate before performing a backward/update pass.'	,)
  parser.add_argument('--seed'	,type=snake_case__	,default=42	,help='random seed for initialization'	)
  parser.add_argument(
      '--data_dir'	,default=snake_case__	,type=snake_case__	,required=snake_case__	,help='The input data dir. Should contain the training files for the CoNLL-2003 NER task.'	,)


def 	a_					(							_lowerCAmelCase	,_lowerCAmelCase	,_lowerCAmelCase=None	,_lowerCAmelCase=True	,_lowerCAmelCase=[]	,_lowerCAmelCase=None	,_lowerCAmelCase=None	,**_lowerCAmelCase	,)				->				str:
  pl.seed_everything(args.seed	)

  # init model
  __lowerCamelCase	:	Union[str, Any]   	=			Path(model.hparams.output_dir	)
  odir.mkdir(exist_ok=snake_case__	)

  # add custom checkpoints
  if checkpoint_callback is None:
    __lowerCamelCase	:	Any   	=			pl.callbacks.ModelCheckpoint(
        filepath=args.output_dir	,prefix='checkpoint'	,monitor='val_loss'	,mode='min'	,save_top_k=1	)
  if early_stopping_callback:
    extra_callbacks.append(snake_case__	)
  if logging_callback is None:
    __lowerCamelCase	:	Union[str, Any]   	=			LoggingCallback()

  __lowerCamelCase	:	List[Any]   	=			{}

  # TODO: remove with PyTorch 1.6 since pl uses native amp
  if args.fpaa:
    __lowerCamelCase	:	Dict   	=			16
    __lowerCamelCase	:	Optional[int]   	=			args.fpaa_opt_level

  if args.gpus > 1:
    __lowerCamelCase	:	Tuple   	=			'ddp'

  __lowerCamelCase	:	Optional[Any]   	=			args.accumulate_grad_batches
  __lowerCamelCase	:	Tuple   	=			extra_train_kwargs.get('accelerator'	,snake_case__	)
  __lowerCamelCase	:	Any   	=			extra_train_kwargs.get('profiler'	,snake_case__	)

  __lowerCamelCase	:	Any   	=			pl.Trainer.from_argparse_args(
      snake_case__	,weights_summary=snake_case__	,callbacks=[logging_callback] + extra_callbacks	,logger=snake_case__	,checkpoint_callback=snake_case__	,**snake_case__	,)

  if args.do_train:
    trainer.fit(snake_case__	)

  return trainer











'''simple docstring'''





from __future__ import annotations

from collections.abc import Iterable






class  lowerCamelCase_   :
  """simple docstring"""




  def __init__(			self				:     int      ,     _a				:     Dict      ,     _a				:     Optional[Any]       ) -> str:
    __lowerCamelCase	,__lowerCamelCase	:	List[Any]   	=			float(_a       ), float(_a       )




  def __eq__(			self				:     Tuple      ,     _a				:     List[Any]       ) -> Optional[int]:
    return self.x == other.x and self.y == other.y




  def __ne__(			self				:     Tuple      ,     _a				:     Optional[int]       ) -> List[str]:
    return not self == other




  def __gt__(			self				:     Tuple      ,     _a				:     str       ) -> str:
    if self.x > other.x:
      return True
    elif self.x == other.x:
      return self.y > other.y
    return False




  def __lt__(			self				:     Union[str, Any]      ,     _a				:     List[Any]       ) -> Optional[Any]:
    return not self > other




  def __ge__(			self				:     Tuple      ,     _a				:     Optional[Any]       ) -> Optional[int]:
    if self.x > other.x:
      return True
    elif self.x == other.x:
      return self.y >= other.y
    return False




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




  def __repr__(			self				:     int       ) -> Optional[int]:
    return f'({self.x}, {self.y})'




  def __hash__(			self				:     Optional[Any]       ) -> Union[str, Any]:
    return hash(self.x       )




def 	a_					(							_lowerCAmelCase	,)				->				list[Point]:
  __lowerCamelCase	:	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 	a_					(							_lowerCAmelCase	)				->				list[Point]:

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

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

  return _construct_points(_lowerCAmelCase	)

def 	a_					(							_lowerCAmelCase	,_lowerCAmelCase	,_lowerCAmelCase	)				->				float:
  __lowerCamelCase	:	Optional[int]   	=			(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	)				->				list[Point]:
  __lowerCamelCase	:	Optional[Any]   	=			sorted(_validate_input(_lowerCAmelCase	)	)
  __lowerCamelCase	:	Optional[int]   	=			len(_lowerCAmelCase	)
  __lowerCamelCase	:	Union[str, Any]   	=			set()

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

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

        if points_left_of_ij and points_right_of_ij:
          __lowerCamelCase	:	int   	=			False
          break

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

  return sorted(_lowerCAmelCase	)

def 	a_					(							_lowerCAmelCase	)				->				list[Point]:
  __lowerCamelCase	:	Dict   	=			sorted(_validate_input(_lowerCAmelCase	)	)
  __lowerCamelCase	:	Optional[Any]   	=			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

  __lowerCamelCase	:	str   	=			points[0]
  __lowerCamelCase	:	Optional[Any]   	=			points[n - 1]

  __lowerCamelCase	:	Tuple   	=			{left_most_point, right_most_point}
  __lowerCamelCase	:	int   	=			[]
  __lowerCamelCase	:	Tuple   	=			[]

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

    for p in points:
      __lowerCamelCase	:	List[str]   	=			_det(_lowerCAmelCase	,_lowerCAmelCase	,_lowerCAmelCase	)

      if det > 0:
        candidate_points.append(_lowerCAmelCase	)

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

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

def 	a_					(							_lowerCAmelCase	)				->				list[Point]:
  __lowerCamelCase	:	Optional[int]   	=			sorted(_validate_input(_lowerCAmelCase	)	)
  __lowerCamelCase	:	List[Any]   	=			len(_lowerCAmelCase	)

  __lowerCamelCase	:	Tuple   	=			points[:2]
  for i in range(2	,_lowerCAmelCase	):
    __lowerCamelCase	:	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:
      __lowerCamelCase	:	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 	a_					(							)				->				Optional[int]:
  __lowerCamelCase	:	List[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)]
  __lowerCamelCase	:	Any   	=			convex_hull_bf(_lowerCAmelCase	)

  __lowerCamelCase	:	Optional[int]   	=			convex_hull_recursive(_lowerCAmelCase	)
  assert results_bf == results_recursive

  __lowerCamelCase	:	int   	=			convex_hull_melkman(_lowerCAmelCase	)
  assert results_bf == results_melkman

  print(_lowerCAmelCase	)


if __name__ == "__main__":
   main()






