






'''simple docstring'''





import json
import logging
import os
import random
import sys
from dataclasses import dataclass, field
from typing import Optional

import evaluate
import numpy as np
import torch
from datasets import load_dataset
from huggingface_hub import hf_hub_download
from PIL import Image
from torch import nn
from torchvision import transforms
from torchvision.transforms import functional

import transformers
from transformers import (
    AutoConfig,
    AutoImageProcessor,
    AutoModelForSemanticSegmentation,
    HfArgumentParser,
    Trainer,
    TrainingArguments,
    default_data_collator,
)
from transformers.trainer_utils import get_last_checkpoint
from transformers.utils import check_min_version, send_example_telemetry
from transformers.utils.versions import require_version
_UpperCamelCase		:		Optional[int]								=			logging.getLogger(__name__)

# Will error if the minimal version of Transformers is not installed. Remove at your own risks.
check_min_version('4.31.0')

require_version('datasets>=2.0.0', 'To fix: pip install -r examples/pytorch/semantic-segmentation/requirements.txt')
def __UpperCAmelCase (			A			:	List[Any]	,   A			:	Any	,   A			:	Dict=0						)  -> str:
			UpperCAmelCase_     :   int       =   (size, size) if isinstance(A	,   A						) else size
			UpperCAmelCase_  ,     UpperCAmelCase_     :   Any       =   img.size
			UpperCAmelCase_     :   int       =   size[1] - original_height if original_height < size[1] else 0
			UpperCAmelCase_     :   Optional[int]       =   size[0] - original_width if original_width < size[0] else 0
			UpperCAmelCase_     :   int       =   functional.pad(A	,   (0, 0, pad_width, pad_height)	,   fill=A						)
			return img


class 				snake_case__     :




					def __init__(       self       :						int							,				_A       :						Union[str, Any]     )  ->    Union[str, Any]:
								UpperCAmelCase_     :   Union[str, Any]       =   transforms





					def __call__(       self       :						Optional[int]							,				_A       :						Optional[Any]							,				_A       :						Dict     )  ->    int:
								for t in self.transforms:
											UpperCAmelCase_  ,     UpperCAmelCase_     :   Optional[Any]       =   t(_A							,				_A     )
								return image, target






class 				snake_case__     :




					def __init__(       self       :						List[str]     )  ->    int:
								pass





					def __call__(       self       :						Optional[Any]							,				_A       :						Dict							,				_A       :						List[str]     )  ->    Union[str, Any]:
								return image, target






class 				snake_case__     :




					def __init__(       self       :						Dict							,				_A       :						Any     )  ->    Optional[Any]:
								UpperCAmelCase_     :   int       =   size





					def __call__(       self       :						Dict							,				_A       :						Optional[Any]							,				_A       :						int     )  ->    Union[str, Any]:
								UpperCAmelCase_     :   Tuple       =   functional.resize(_A							,				self.size     )
								UpperCAmelCase_     :   Optional[int]       =   functional.resize(_A							,				self.size							,				interpolation=transforms.InterpolationMode.NEAREST     )
								return image, target






class 				snake_case__     :




					def __init__(       self       :						str							,				_A       :						Optional[Any]							,				_A       :						List[Any]=None     )  ->    str:
								UpperCAmelCase_     :   Tuple       =   min_size
								if max_size is None:
											UpperCAmelCase_     :   Dict       =   min_size
								UpperCAmelCase_     :   Tuple       =   max_size





					def __call__(       self       :						Any							,				_A       :						List[Any]							,				_A       :						Optional[int]     )  ->    Optional[Any]:
								UpperCAmelCase_     :   Optional[int]       =   random.randint(self.min_size							,				self.max_size     )
								UpperCAmelCase_     :   str       =   functional.resize(_A							,				_A     )
								UpperCAmelCase_     :   str       =   functional.resize(_A							,				_A							,				interpolation=transforms.InterpolationMode.NEAREST     )
								return image, target






class 				snake_case__     :




					def __init__(       self       :						List[str]							,				_A       :						Union[str, Any]     )  ->    Union[str, Any]:
								UpperCAmelCase_     :   Dict       =   size if isinstance(_A							,				_A     ) else (size, size)





					def __call__(       self       :						Tuple							,				_A       :						Dict							,				_A       :						Tuple     )  ->    List[str]:
								UpperCAmelCase_     :   Optional[Any]       =   pad_if_smaller(_A							,				self.size     )
								UpperCAmelCase_     :   int       =   pad_if_smaller(_A							,				self.size							,				fill=2_55     )
								UpperCAmelCase_     :   List[str]       =   transforms.RandomCrop.get_params(_A							,				self.size     )
								UpperCAmelCase_     :   List[Any]       =   functional.crop(_A							,				*_A     )
								UpperCAmelCase_     :   Any       =   functional.crop(_A							,				*_A     )
								return image, target






class 				snake_case__     :




					def __init__(       self       :						Dict							,				_A       :						Optional[Any]     )  ->    List[Any]:
								UpperCAmelCase_     :   Union[str, Any]       =   flip_prob





					def __call__(       self       :						Union[str, Any]							,				_A       :						Any							,				_A       :						Optional[int]     )  ->    str:
								if random.random() < self.flip_prob:
											UpperCAmelCase_     :   Dict       =   functional.hflip(_A     )
											UpperCAmelCase_     :   Dict       =   functional.hflip(_A     )
								return image, target






class 				snake_case__     :




					def __call__(       self       :						List[str]							,				_A       :						str							,				_A       :						Optional[int]     )  ->    Dict:
								UpperCAmelCase_     :   Union[str, Any]       =   functional.pil_to_tensor(_A     )
								UpperCAmelCase_     :   str       =   torch.as_tensor(np.array(_A     )							,				dtype=torch.intaa     )
								return image, target






class 				snake_case__     :




					def __init__(       self       :						Tuple							,				_A       :						str     )  ->    int:
								UpperCAmelCase_     :   Dict       =   dtype





					def __call__(       self       :						Dict							,				_A       :						Union[str, Any]							,				_A       :						Any     )  ->    Optional[Any]:
								UpperCAmelCase_     :   Union[str, Any]       =   functional.convert_image_dtype(_A							,				self.dtype     )
								return image, target






class 				snake_case__     :




					def __init__(       self       :						Tuple							,				_A       :						Tuple							,				_A       :						int     )  ->    Any:
								UpperCAmelCase_     :   Tuple       =   mean
								UpperCAmelCase_     :   int       =   std





					def __call__(       self       :						Dict							,				_A       :						List[str]							,				_A       :						List[Any]     )  ->    Union[str, Any]:
								UpperCAmelCase_     :   Union[str, Any]       =   functional.normalize(_A							,				mean=self.mean							,				std=self.std     )
								return image, target






class 				snake_case__     :




					def __call__(       self       :						int							,				_A       :						List[Any]							,				_A       :						int     )  ->    Union[str, Any]:
								if not isinstance(_A							,				np.ndarray     ):
											UpperCAmelCase_     :   str       =   np.array(_A     ).astype(np.uinta     )
								# avoid using underflow conversion
								UpperCAmelCase_     :   Tuple       =   2_55
								UpperCAmelCase_     :   List[str]       =   target - 1
								UpperCAmelCase_     :   Dict       =   2_55

								UpperCAmelCase_     :   int       =   Image.fromarray(_A     )
								return image, target






@dataclass
class 				snake_case__     :
					a_       =			field(
					    default="segments/sidewalk-semantic"      ,							metadata={
					        "help": "Name of a dataset from the hub (could be your own, possibly private dataset hosted on the hub)."
					    }      ,							)
					a_       =			field(
					    default=UpperCamelCase      ,							metadata={"help": "The configuration name of the dataset to use (via the datasets library)."})
					a_       =			field(
					    default=0.15      ,							metadata={"help": "Percent to split off of train for validation."})
					a_       =			field(
					    default=UpperCamelCase      ,							metadata={
					        "help": (
					            "For debugging purposes or quicker training, truncate the number of training examples to this "
					            "value if set."
					        )
					    }      ,							)
					a_       =			field(
					    default=UpperCamelCase      ,							metadata={
					        "help": (
					            "For debugging purposes or quicker training, truncate the number of evaluation examples to this "
					            "value if set."
					        )
					    }      ,							)
					a_       =			field(
					    default=UpperCamelCase      ,							metadata={"help": "Whether or not to reduce all labels by 1 and replace background by 255."}      ,							)




					def 						A     (       self       :						Optional[int]     )  ->    Optional[int]:
								if self.dataset_name is None and (self.train_dir is None and self.validation_dir is None):
											raise ValueError(
											    '''You must specify either a dataset name from the hub or a train and/or validation directory.'''     )






@dataclass
class 				snake_case__     :
					a_       =			field(
					    default="nvidia/mit-b0"      ,							metadata={"help": "Path to pretrained model or model identifier from huggingface.co/models"}      ,							)
					a_       =			field(
					    default=UpperCamelCase      ,							metadata={"help": "Pretrained config name or path if not the same as model_name"})
					a_       =			field(
					    default=UpperCamelCase      ,							metadata={"help": "Where do you want to store the pretrained models downloaded from s3"})
					a_       =			field(
					    default="main"      ,							metadata={"help": "The specific model version to use (can be a branch name, tag name or commit id)."}      ,							)
					a_       =			field(default=UpperCamelCase      ,							metadata={"help": "Name or path of preprocessor config."})
					a_       =			field(
					    default=UpperCamelCase      ,							metadata={
					        "help": (
					            "Will use the token generated when running `huggingface-cli login` (necessary to use this script "
					            "with private models)."
					        )
					    }      ,							)






def __UpperCAmelCase (			)  -> Dict:
			# See all possible arguments in src/transformers/training_args.py
			# or by passing the --help flag to this script.
			# We now keep distinct sets of args, for a cleaner separation of concerns.

			UpperCAmelCase_     :   Union[str, Any]       =   HfArgumentParser((ModelArguments, DataTrainingArguments, TrainingArguments)						)
			if len(sys.argv						) == 2 and sys.argv[1].endswith('''.json'''						):
						# If we pass only one argument to the script and it's the path to a json file,
						# let's parse it to get our arguments.
						UpperCAmelCase_  ,     UpperCAmelCase_  ,     UpperCAmelCase_     :   Any       =   parser.parse_json_file(json_file=os.path.abspath(sys.argv[1]						)						)
			else:
						UpperCAmelCase_  ,     UpperCAmelCase_  ,     UpperCAmelCase_     :   Union[str, Any]       =   parser.parse_args_into_dataclasses()

			# Sending telemetry. Tracking the example usage helps us better allocate resources to maintain them. The
			# information sent is the one passed as arguments along with your Python/PyTorch versions.
			send_example_telemetry('''run_semantic_segmentation'''	,   A	,   A						)

			# Setup logging
			logging.basicConfig(
			    format='''%(asctime)s - %(levelname)s - %(name)s - %(message)s'''	,   datefmt='''%m/%d/%Y %H:%M:%S'''	,   handlers=[logging.StreamHandler(sys.stdout						)]	,   )

			if training_args.should_log:
						# The default of training_args.log_level is passive, so we set log level at info here to have that default.
						transformers.utils.logging.set_verbosity_info()

			UpperCAmelCase_     :   List[str]       =   training_args.get_process_log_level()
			logger.setLevel(A						)
			transformers.utils.logging.set_verbosity(A						)
			transformers.utils.logging.enable_default_handler()
			transformers.utils.logging.enable_explicit_format()

			# Log on each process the small summary:
			logger.warning(
			    F"Process rank: {training_args.local_rank}, device: {training_args.device}, n_gpu: {training_args.n_gpu}"
			    + F"distributed training: {bool(training_args.local_rank != -1						)}, 16-bits training: {training_args.fpaa}"						)
			logger.info(F"Training/evaluation parameters {training_args}"						)

			# Detecting last checkpoint.
			UpperCAmelCase_     :   List[Any]       =   None
			if os.path.isdir(training_args.output_dir						) and training_args.do_train and not training_args.overwrite_output_dir:
						UpperCAmelCase_     :   List[Any]       =   get_last_checkpoint(training_args.output_dir						)
						if last_checkpoint is None and len(os.listdir(training_args.output_dir						)						) > 0:
									raise ValueError(
									    F"Output directory ({training_args.output_dir}) already exists and is not empty. "
									    '''Use --overwrite_output_dir to overcome.'''						)
						elif last_checkpoint is not None and training_args.resume_from_checkpoint is None:
									logger.info(
									    F"Checkpoint detected, resuming training at {last_checkpoint}. To avoid this behavior, change "
									    '''the `--output_dir` or add `--overwrite_output_dir` to train from scratch.'''						)

    # Load dataset
    # In distributed training, the load_dataset function guarantees that only one local process can concurrently
    # download the dataset.
    # TODO support datasets from local folders
			UpperCAmelCase_     :   int       =   load_dataset(data_args.dataset_name	,   cache_dir=model_args.cache_dir						)

			# Rename column names to standardized names (only "image" and "label" need to be present)
			if "pixel_values" in dataset["train"].column_names:
						UpperCAmelCase_     :   Union[str, Any]       =   dataset.rename_columns({'''pixel_values''': '''image'''}						)
			if "annotation" in dataset["train"].column_names:
						UpperCAmelCase_     :   str       =   dataset.rename_columns({'''annotation''': '''label'''}						)

			# If we don't have a validation split, split off a percentage of train as validation.
			UpperCAmelCase_     :   str       =   None if '''validation''' in dataset.keys() else data_args.train_val_split
			if isinstance(data_args.train_val_split	,   A						) and data_args.train_val_split > 0.0:
						UpperCAmelCase_     :   str       =   dataset['''train'''].train_test_split(data_args.train_val_split						)
						UpperCAmelCase_     :   int       =   split['''train''']
						UpperCAmelCase_     :   List[str]       =   split['''test''']

			# Prepare label mappings.
			# We'll include these in the model's config to get human readable labels in the Inference API.
			if data_args.dataset_name == "scene_parse_150":
						UpperCAmelCase_     :   List[Any]       =   '''huggingface/label-files'''
						UpperCAmelCase_     :   Union[str, Any]       =   '''ade20k-id2label.json'''
			else:
						UpperCAmelCase_     :   Tuple       =   data_args.dataset_name
						UpperCAmelCase_     :   Dict       =   '''id2label.json'''
			UpperCAmelCase_     :   Optional[int]       =   json.load(open(hf_hub_download(A	,   A	,   repo_type='''dataset'''						)	,   '''r'''						)						)
			UpperCAmelCase_     :   str       =   {int(A						): v for k, v in idalabel.items()}
			UpperCAmelCase_     :   Dict       =   {v: str(A						) for k, v in idalabel.items()}

			# Load the mean IoU metric from the datasets package
			UpperCAmelCase_     :   str       =   evaluate.load('''mean_iou'''						)

			# Define our compute_metrics function. It takes an `EvalPrediction` object (a namedtuple with a
			# predictions and label_ids field) and has to return a dictionary string to float.
			@torch.no_grad()
			def compute_metrics(A			:	Dict						):
						UpperCAmelCase_  ,     UpperCAmelCase_     :   Dict       =   eval_pred
						UpperCAmelCase_     :   List[Any]       =   torch.from_numpy(A						)
						# scale the logits to the size of the label
						UpperCAmelCase_     :   str       =   nn.functional.interpolate(
						    A	,   size=labels.shape[-2:]	,   mode='''bilinear'''	,   align_corners=A	,   ).argmax(dim=1						)

						UpperCAmelCase_     :   Dict       =   logits_tensor.detach().cpu().numpy()
						UpperCAmelCase_     :   Union[str, Any]       =   metric.compute(
						    predictions=A	,   references=A	,   num_labels=len(A						)	,   ignore_index=0	,   reduce_labels=image_processor.do_reduce_labels	,   )
						# add per category metrics as individual key-value pairs
						UpperCAmelCase_     :   List[Any]       =   metrics.pop('''per_category_accuracy'''						).tolist()
						UpperCAmelCase_     :   List[Any]       =   metrics.pop('''per_category_iou'''						).tolist()

						metrics.update({F"accuracy_{idalabel[i]}": v for i, v in enumerate(A						)}						)
						metrics.update({F"iou_{idalabel[i]}": v for i, v in enumerate(A						)}						)

						return metrics

			UpperCAmelCase_     :   Union[str, Any]       =   AutoConfig.from_pretrained(
			    model_args.config_name or model_args.model_name_or_path	,   labelaid=A	,   idalabel=A	,   cache_dir=model_args.cache_dir	,   revision=model_args.model_revision	,   use_auth_token=True if model_args.use_auth_token else None	,   )
			UpperCAmelCase_     :   Dict       =   AutoModelForSemanticSegmentation.from_pretrained(
			    model_args.model_name_or_path	,   from_tf=bool('''.ckpt''' in model_args.model_name_or_path						)	,   config=A	,   cache_dir=model_args.cache_dir	,   revision=model_args.model_revision	,   use_auth_token=True if model_args.use_auth_token else None	,   )
			UpperCAmelCase_     :   int       =   AutoImageProcessor.from_pretrained(
			    model_args.image_processor_name or model_args.model_name_or_path	,   cache_dir=model_args.cache_dir	,   revision=model_args.model_revision	,   use_auth_token=True if model_args.use_auth_token else None	,   )

			# Define torchvision transforms to be applied to each image + target.
			# Not that straightforward in torchvision: https://github.com/pytorch/vision/issues/9
			# Currently based on official torchvision references: https://github.com/pytorch/vision/blob/main/references/segmentation/transforms.py
			if "shortest_edge" in image_processor.size:
						# We instead set the target size as (shortest_edge, shortest_edge) to here to ensure all images are batchable.
						UpperCAmelCase_     :   Dict       =   (image_processor.size['''shortest_edge'''], image_processor.size['''shortest_edge'''])
			else:
						UpperCAmelCase_     :   Dict       =   (image_processor.size['''height'''], image_processor.size['''width'''])
			UpperCAmelCase_     :   str       =   Compose(
			    [
			        ReduceLabels() if data_args.reduce_labels else Identity(),
			        RandomCrop(size=A						),
			        RandomHorizontalFlip(flip_prob=0.5						),
			        PILToTensor(),
			        ConvertImageDtype(torch.float						),
			        Normalize(mean=image_processor.image_mean	,   std=image_processor.image_std						),
			    ]						)
			# Define torchvision transform to be applied to each image.
			# jitter = ColorJitter(brightness=0.25, contrast=0.25, saturation=0.25, hue=0.1)
			UpperCAmelCase_     :   int       =   Compose(
			    [
			        ReduceLabels() if data_args.reduce_labels else Identity(),
			        Resize(size=A						),
			        PILToTensor(),
			        ConvertImageDtype(torch.float						),
			        Normalize(mean=image_processor.image_mean	,   std=image_processor.image_std						),
			    ]						)

			def preprocess_train(A			:	Tuple						):
						UpperCAmelCase_     :   str       =   []
						UpperCAmelCase_     :   Tuple       =   []
						for image, target in zip(example_batch['''image''']	,   example_batch['''label''']						):
									UpperCAmelCase_  ,     UpperCAmelCase_     :   int       =   train_transforms(image.convert('''RGB'''						)	,   A						)
									pixel_values.append(A						)
									labels.append(A						)

						UpperCAmelCase_     :   Optional[int]       =   {}
						UpperCAmelCase_     :   Tuple       =   torch.stack(A						)
						UpperCAmelCase_     :   List[str]       =   torch.stack(A						)

						return encoding

			def preprocess_val(A			:	List[str]						):
						UpperCAmelCase_     :   str       =   []
						UpperCAmelCase_     :   Any       =   []
						for image, target in zip(example_batch['''image''']	,   example_batch['''label''']						):
									UpperCAmelCase_  ,     UpperCAmelCase_     :   List[Any]       =   val_transforms(image.convert('''RGB'''						)	,   A						)
									pixel_values.append(A						)
									labels.append(A						)

						UpperCAmelCase_     :   Optional[Any]       =   {}
						UpperCAmelCase_     :   Tuple       =   torch.stack(A						)
						UpperCAmelCase_     :   List[Any]       =   torch.stack(A						)

						return encoding

			if training_args.do_train:
						if "train" not in dataset:
									raise ValueError('''--do_train requires a train dataset'''						)
						if data_args.max_train_samples is not None:
									UpperCAmelCase_     :   int       =   (
									    dataset['''train'''].shuffle(seed=training_args.seed						).select(range(data_args.max_train_samples						)						)
									)
						# Set the training transforms
						dataset["train"].set_transform(A						)

			if training_args.do_eval:
						if "validation" not in dataset:
									raise ValueError('''--do_eval requires a validation dataset'''						)
						if data_args.max_eval_samples is not None:
									UpperCAmelCase_     :   Tuple       =   (
									    dataset['''validation'''].shuffle(seed=training_args.seed						).select(range(data_args.max_eval_samples						)						)
									)
						# Set the validation transforms
						dataset["validation"].set_transform(A						)

			# Initalize our trainer
			UpperCAmelCase_     :   Dict       =   Trainer(
			    model=A	,   args=A	,   train_dataset=dataset['''train'''] if training_args.do_train else None	,   eval_dataset=dataset['''validation'''] if training_args.do_eval else None	,   compute_metrics=A	,   tokenizer=A	,   data_collator=A	,   )

			# Training
			if training_args.do_train:
						UpperCAmelCase_     :   str       =   None
						if training_args.resume_from_checkpoint is not None:
									UpperCAmelCase_     :   int       =   training_args.resume_from_checkpoint
						elif last_checkpoint is not None:
									UpperCAmelCase_     :   List[Any]       =   last_checkpoint
						UpperCAmelCase_     :   Optional[Any]       =   trainer.train(resume_from_checkpoint=A						)
						trainer.save_model()
						trainer.log_metrics('''train'''	,   train_result.metrics						)
						trainer.save_metrics('''train'''	,   train_result.metrics						)
						trainer.save_state()

			# Evaluation
			if training_args.do_eval:
						UpperCAmelCase_     :   Tuple       =   trainer.evaluate()
						trainer.log_metrics('''eval'''	,   A						)
						trainer.save_metrics('''eval'''	,   A						)

			# Write model card and (optionally) push to hub
			UpperCAmelCase_     :   Dict       =   {
			    '''finetuned_from''': model_args.model_name_or_path,
			    '''dataset''': data_args.dataset_name,
			    '''tags''': ['''image-segmentation''', '''vision'''],
			}
			if training_args.push_to_hub:
						trainer.push_to_hub(**A						)
			else:
						trainer.create_model_card(**A						)


if __name__ == "__main__":
						main()










'''simple docstring'''





from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize


class 				snake_case__     (			UpperCamelCase):
					a_       =			1
					a_       =			2
					a_       =			3




					def __repr__(       self       :						str     )  ->    Optional[int]:
								return F"{self.__class__.__name__}.{self.name}"






def __UpperCAmelCase (			A			:	tuple[int, int]	,   A			:	int	,   A			:	int						)  -> float:
			UpperCAmelCase_  ,     UpperCAmelCase_     :   Any       =   point
			return degrees(atana(y - miny	,   x - minx						)						)
def __UpperCAmelCase (			A			:	tuple[int, int]	,   A			:	tuple[int, int]	,   A			:	tuple[int, int]						)  -> Direction:
			UpperCAmelCase_  ,     UpperCAmelCase_     :   Tuple       =   starting
			UpperCAmelCase_  ,     UpperCAmelCase_     :   Optional[Any]       =   via
			UpperCAmelCase_  ,     UpperCAmelCase_     :   Optional[int]       =   target
			UpperCAmelCase_     :   Optional[int]       =   degrees(atana(ya - ya	,   xa - xa						)						)
			via_angle %= 3_6_0
			UpperCAmelCase_     :   Dict       =   degrees(atana(ya - ya	,   xa - xa						)						)
			target_angle %= 3_6_0
			# t-
			#  \ \
			#   \ v
			#    \|
			#     s
			# via_angle is always lower than target_angle, if direction is left.
			# If they are same, it means they are on a same line of convex hull.
			if target_angle > via_angle:
						return Direction.left
			elif target_angle == via_angle:
						return Direction.straight
			else:
						return Direction.right







def __UpperCAmelCase (			A			:	list[tuple[int, int]]						)  -> list[tuple[int, int]]:

			if len(A						) <= 2:
						# There is no convex hull
						raise ValueError('''graham_scan: argument must contain more than 3 points.'''						)
			if len(A						) == 3:
						return points
			# find the lowest and the most left point
			UpperCAmelCase_     :   List[str]       =   0
			UpperCAmelCase_  ,     UpperCAmelCase_     :   List[Any]       =   maxsize, maxsize
			for i, point in enumerate(A						):
						UpperCAmelCase_     :   str       =   point[0]
						UpperCAmelCase_     :   List[Any]       =   point[1]
						if y < miny:
									UpperCAmelCase_     :   int       =   y
									UpperCAmelCase_     :   Dict       =   x
									UpperCAmelCase_     :   Any       =   i
						if y == miny and x < minx:
									UpperCAmelCase_     :   str       =   x
									UpperCAmelCase_     :   Optional[int]       =   i

    # remove the lowest and the most left point from points for preparing for sort
			points.pop(A						)

			UpperCAmelCase_     :   Optional[Any]       =   sorted(A	,   key=lambda A						: angle_comparer(A	,   A	,   A						)						)
			# This insert actually costs complexity,
			# and you should instead add (minx, miny) into stack later.
			# I'm using insert just for easy understanding.
			sorted_points.insert(0	,   (minx, miny)						)

			UpperCAmelCase_     :   deque[tuple[int, int]]       =   deque()
			stack.append(sorted_points[0]						)
			stack.append(sorted_points[1]						)
			stack.append(sorted_points[2]						)
			# In any ways, the first 3 points line are towards left.
			# Because we sort them the angle from minx, miny.
			UpperCAmelCase_     :   Any       =   Direction.left

			for i in range(3	,   len(A						)						):
						while True:
									UpperCAmelCase_     :   Any       =   stack[-2]
									UpperCAmelCase_     :   List[Any]       =   stack[-1]
									UpperCAmelCase_     :   Any       =   sorted_points[i]
									UpperCAmelCase_     :   Tuple       =   check_direction(A	,   A	,   A						)

									if next_direction == Direction.left:
												UpperCAmelCase_     :   Optional[Any]       =   Direction.left
												break
									if next_direction == Direction.straight:
												if current_direction == Direction.left:
															# We keep current_direction as left.
															# Because if the straight line keeps as straight,
															# we want to know if this straight line is towards left.
															break
												elif current_direction == Direction.right:
															# If the straight line is towards right,
															# every previous points on those straigh line is not convex hull.
															stack.pop()
									if next_direction == Direction.right:
												stack.pop()
						stack.append(sorted_points[i]						)
			return list(A						)


