




'''simple docstring'''






from __future__ import annotations

from collections.abc import Iterable



class    A						:




				'''simple docstring'''





				def __init__(self					,    _UpperCAmelCase					,    _UpperCAmelCase     )      ->			Tuple:
							__UpperCamelCase						,   __UpperCamelCase :     int										=  float(_UpperCAmelCase     ), float(_UpperCAmelCase     )
				def __eq__(self					,    _UpperCAmelCase     )      ->			int:
							return self.x == other.x and self.y == other.y
				def __ne__(self					,    _UpperCAmelCase     )      ->			int:
							return not self == other
				def __gt__(self					,    _UpperCAmelCase     )      ->			str:
							if self.x > other.x:
										return True
							elif self.x == other.x:
										return self.y > other.y
							return False
				def __lt__(self					,    _UpperCAmelCase     )      ->			List[Any]:
							return not self > other
				def __ge__(self					,    _UpperCAmelCase     )      ->			Optional[int]:
							if self.x > other.x:
										return True
							elif self.x == other.x:
										return self.y >= other.y
							return False
				def __le__(self					,    _UpperCAmelCase     )      ->			Optional[Any]:
							if self.x < other.x:
										return True
							elif self.x == other.x:
										return self.y <= other.y
							return False
				def __repr__(self     )      ->			Dict:
							return f"({self.x}, {self.y})"





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







def      __lowerCAmelCase   (       snake_case__   , ):
			__UpperCamelCase :     list[Point]										=  []
			if list_of_tuples:
						for p in list_of_tuples:
									if isinstance(snake_case__   , snake_case__		):
												points.append(snake_case__		)
									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      __lowerCAmelCase   (       snake_case__		):

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

			if not points:
						__UpperCamelCase :     str										=  F"Expecting a list of points but got {points}"
						raise ValueError(snake_case__		)

			return _construct_points(snake_case__		)

def      __lowerCAmelCase   (       snake_case__   , snake_case__   , snake_case__		):
			__UpperCamelCase :     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      __lowerCAmelCase   (       snake_case__		):
			__UpperCamelCase :     List[str]										=  sorted(_validate_input(snake_case__		)		)
			__UpperCamelCase :     Union[str, Any]										=  len(snake_case__		)
			__UpperCamelCase :     Optional[int]										=  set()

			for i in range(n - 1		):
						for j in range(i + 1   , snake_case__		):
									__UpperCamelCase :     int										=  False
									__UpperCamelCase :     Optional[int]										=  True
									for k in range(snake_case__		):
												if k != i and k != j:
															__UpperCamelCase :     Any										=  _det(points[i]   , points[j]   , points[k]		)

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

												if points_left_of_ij and points_right_of_ij:
															__UpperCamelCase :     Any										=  False
															break

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

			return sorted(snake_case__		)

def      __lowerCAmelCase   (       snake_case__		):
			__UpperCamelCase :     Tuple										=  sorted(_validate_input(snake_case__		)		)
			__UpperCamelCase :     Union[str, Any]										=  len(snake_case__		)

			# divide all the points into an upper hull and a lower hull
			# the left most point and the right most point are definitely
			# members of the convex hull by definition.
			# use these two anchors to divide all the points into two hulls,
			# an upper hull and a lower hull.

			# all points to the left (above) the line joining the extreme points belong to the
			# upper hull
			# all points to the right (below) the line joining the extreme points below to the
			# lower hull
			# ignore all points on the line joining the extreme points since they cannot be
			# part of the convex hull

			__UpperCamelCase :     Any										=  points[0]
			__UpperCamelCase :     List[str]										=  points[n - 1]

			__UpperCamelCase :     Optional[Any]										=  {left_most_point, right_most_point}
			__UpperCamelCase :     Tuple										=  []
			__UpperCamelCase :     Dict										=  []

			for i in range(1   , n - 1		):
						__UpperCamelCase :     int										=  _det(snake_case__   , snake_case__   , points[i]		)

						if det > 0:
									upper_hull.append(points[i]		)
						elif det < 0:
									lower_hull.append(points[i]		)

			_construct_hull(snake_case__   , snake_case__   , snake_case__   , snake_case__		)
			_construct_hull(snake_case__   , snake_case__   , snake_case__   , snake_case__		)

			return sorted(snake_case__		)

def      __lowerCAmelCase   (       snake_case__   , snake_case__   , snake_case__   , snake_case__		):
			if points:
						__UpperCamelCase :     List[str]										=  None
						__UpperCamelCase :     Optional[int]										=  float("-inf"		)
						__UpperCamelCase :     Optional[int]										=  []

						for p in points:
									__UpperCamelCase :     Optional[Any]										=  _det(snake_case__   , snake_case__   , snake_case__		)

									if det > 0:
												candidate_points.append(snake_case__		)

												if det > extreme_point_distance:
															__UpperCamelCase :     Optional[Any]										=  det
															__UpperCamelCase :     str										=  p

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

def      __lowerCAmelCase   (       snake_case__		):
			__UpperCamelCase :     Optional[int]										=  sorted(_validate_input(snake_case__		)		)
			__UpperCamelCase :     List[str]										=  len(snake_case__		)

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

			for j in range(snake_case__   , snake_case__		):
						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(snake_case__		) > 3 else convex_hull		)

def      __lowerCAmelCase   (       ):
			__UpperCamelCase :     int										=  [
			    (0, 3),
			    (2, 2),
			    (1, 1),
			    (2, 1),
			    (3, 0),
			    (0, 0),
			    (3, 3),
			    (2, -1),
			    (2, -4),
			    (1, -3),
			]
			# the convex set of points is
			# [(0, 0), (0, 3), (1, -3), (2, -4), (3, 0), (3, 3)]
			__UpperCamelCase :     Optional[Any]										=  convex_hull_bf(snake_case__		)

			__UpperCamelCase :     int										=  convex_hull_recursive(snake_case__		)
			assert results_bf == results_recursive

			__UpperCamelCase :     List[str]										=  convex_hull_melkman(snake_case__		)
			assert results_bf == results_melkman

			print(snake_case__		)


if __name__ == "__main__":
				main()









'''simple docstring'''






import tempfile
import unittest

from transformers import DPRConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

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


if is_torch_available():
				import torch

				from transformers import DPRContextEncoder, DPRQuestionEncoder, DPRReader, DPRReaderTokenizer
				from transformers.models.dpr.modeling_dpr import (
				    DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
				    DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
				    DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST,
				)



class    A						:




				'''simple docstring'''





				def __init__(self					,    _UpperCAmelCase					,    _UpperCAmelCase=1_3					,    _UpperCAmelCase=7					,    _UpperCAmelCase=False					,    _UpperCAmelCase=True					,    _UpperCAmelCase=True					,    _UpperCAmelCase=True					,    _UpperCAmelCase=9_9					,    _UpperCAmelCase=3_2					,    _UpperCAmelCase=5					,    _UpperCAmelCase=4					,    _UpperCAmelCase=3_7					,    _UpperCAmelCase="gelu"					,    _UpperCAmelCase=0.1					,    _UpperCAmelCase=0.1					,    _UpperCAmelCase=5_1_2					,    _UpperCAmelCase=1_6					,    _UpperCAmelCase=2					,    _UpperCAmelCase=0.02					,    _UpperCAmelCase=3					,    _UpperCAmelCase=4					,    _UpperCAmelCase=None					,    _UpperCAmelCase=0					,    )      ->			List[Any]:
							__UpperCamelCase :     List[str]										=  parent
							__UpperCamelCase :     Optional[int]										=  batch_size
							__UpperCamelCase :     Union[str, Any]										=  seq_length
							__UpperCamelCase :     List[Any]										=  is_training
							__UpperCamelCase :     Union[str, Any]										=  use_input_mask
							__UpperCamelCase :     int										=  use_token_type_ids
							__UpperCamelCase :     Any										=  use_labels
							__UpperCamelCase :     Union[str, Any]										=  vocab_size
							__UpperCamelCase :     Any										=  hidden_size
							__UpperCamelCase :     Dict										=  num_hidden_layers
							__UpperCamelCase :     List[Any]										=  num_attention_heads
							__UpperCamelCase :     Union[str, Any]										=  intermediate_size
							__UpperCamelCase :     Tuple										=  hidden_act
							__UpperCamelCase :     int										=  hidden_dropout_prob
							__UpperCamelCase :     Optional[Any]										=  attention_probs_dropout_prob
							__UpperCamelCase :     List[str]										=  max_position_embeddings
							__UpperCamelCase :     str										=  type_vocab_size
							__UpperCamelCase :     str										=  type_sequence_label_size
							__UpperCamelCase :     List[str]										=  initializer_range
							__UpperCamelCase :     List[str]										=  num_labels
							__UpperCamelCase :     Any										=  num_choices
							__UpperCamelCase :     List[Any]										=  scope
							__UpperCamelCase :     Tuple										=  projection_dim
				def 			a_			(self     )      ->			Any:
							__UpperCamelCase :     str										=  ids_tensor([self.batch_size, self.seq_length]					,    self.vocab_size     )

							__UpperCamelCase :     Dict										=  None
							if self.use_input_mask:
										__UpperCamelCase :     List[str]										=  random_attention_mask([self.batch_size, self.seq_length]     )

							__UpperCamelCase :     Tuple										=  None
							if self.use_token_type_ids:
										__UpperCamelCase :     Optional[int]										=  ids_tensor([self.batch_size, self.seq_length]					,    self.type_vocab_size     )

							__UpperCamelCase :     List[Any]										=  None
							__UpperCamelCase :     Optional[Any]										=  None
							__UpperCamelCase :     List[str]										=  None
							if self.use_labels:
										__UpperCamelCase :     Dict										=  ids_tensor([self.batch_size]					,    self.type_sequence_label_size     )
										__UpperCamelCase :     Any										=  ids_tensor([self.batch_size, self.seq_length]					,    self.num_labels     )
										__UpperCamelCase :     str										=  ids_tensor([self.batch_size]					,    self.num_choices     )

							__UpperCamelCase :     Optional[int]										=  self.get_config()

							return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels
				def 			a_			(self     )      ->			Optional[Any]:
							return DPRConfig(
							    projection_dim=self.projection_dim					,    vocab_size=self.vocab_size					,    hidden_size=self.hidden_size					,    num_hidden_layers=self.num_hidden_layers					,    num_attention_heads=self.num_attention_heads					,    intermediate_size=self.intermediate_size					,    hidden_act=self.hidden_act					,    hidden_dropout_prob=self.hidden_dropout_prob					,    attention_probs_dropout_prob=self.attention_probs_dropout_prob					,    max_position_embeddings=self.max_position_embeddings					,    type_vocab_size=self.type_vocab_size					,    initializer_range=self.initializer_range					,    )
				def 			a_			(self					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase     )      ->			str:
							__UpperCamelCase :     Optional[int]										=  DPRContextEncoder(config=_UpperCAmelCase     )
							model.to(_UpperCAmelCase     )
							model.eval()
							__UpperCamelCase :     Optional[int]										=  model(_UpperCAmelCase					,    attention_mask=_UpperCAmelCase					,    token_type_ids=_UpperCAmelCase     )
							__UpperCamelCase :     Optional[int]										=  model(_UpperCAmelCase					,    token_type_ids=_UpperCAmelCase     )
							__UpperCamelCase :     int										=  model(_UpperCAmelCase     )
							self.parent.assertEqual(result.pooler_output.shape					,    (self.batch_size, self.projection_dim or self.hidden_size)     )
				def 			a_			(self					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase     )      ->			Optional[int]:
							__UpperCamelCase :     int										=  DPRQuestionEncoder(config=_UpperCAmelCase     )
							model.to(_UpperCAmelCase     )
							model.eval()
							__UpperCamelCase :     Optional[int]										=  model(_UpperCAmelCase					,    attention_mask=_UpperCAmelCase					,    token_type_ids=_UpperCAmelCase     )
							__UpperCamelCase :     List[str]										=  model(_UpperCAmelCase					,    token_type_ids=_UpperCAmelCase     )
							__UpperCamelCase :     Optional[Any]										=  model(_UpperCAmelCase     )
							self.parent.assertEqual(result.pooler_output.shape					,    (self.batch_size, self.projection_dim or self.hidden_size)     )
				def 			a_			(self					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase     )      ->			str:
							__UpperCamelCase :     Optional[int]										=  DPRReader(config=_UpperCAmelCase     )
							model.to(_UpperCAmelCase     )
							model.eval()
							__UpperCamelCase :     Optional[Any]										=  model(
							    _UpperCAmelCase					,    attention_mask=_UpperCAmelCase					,    )

							self.parent.assertEqual(result.start_logits.shape					,    (self.batch_size, self.seq_length)     )
							self.parent.assertEqual(result.end_logits.shape					,    (self.batch_size, self.seq_length)     )
							self.parent.assertEqual(result.relevance_logits.shape					,    (self.batch_size,)     )





				def 			a_			(self     )      ->			List[Any]:
							__UpperCamelCase :     Tuple										=  self.prepare_config_and_inputs()
							(
							    (
							    __UpperCamelCase
							)						,   (
							    __UpperCamelCase
							)						,   (
							    __UpperCamelCase
							)						,   (
							    __UpperCamelCase
							)						,   (
							    __UpperCamelCase
							)						,   (
							    __UpperCamelCase
							)						,   (
							    __UpperCamelCase
							)						,   
							) :     Optional[int]										=  config_and_inputs
							__UpperCamelCase :     Dict										=  {"input_ids": input_ids}
							return config, inputs_dict







@require_torch
class    A						(					SCREAMING_SNAKE_CASE__     ,				SCREAMING_SNAKE_CASE__     ,				unittest.TestCase						):




				'''simple docstring'''





				A       =							(
				    (
				        DPRContextEncoder,
				        DPRQuestionEncoder,
				        DPRReader,
				    )
				    if is_torch_available()
				    else ()
				)
				A       =							{"feature-extraction": DPRQuestionEncoder} if is_torch_available() else {}

				A       =							False
				A       =							False  # why?
				A       =							False
				A       =							False
				def 			a_			(self     )      ->			Union[str, Any]:
							__UpperCamelCase :     Dict										=  DPRModelTester(self     )
							__UpperCamelCase :     Tuple										=  ConfigTester(self					,    config_class=_UpperCAmelCase					,    hidden_size=3_7     )
				def 			a_			(self     )      ->			List[str]:
							self.config_tester.run_common_tests()
				def 			a_			(self     )      ->			Optional[int]:
							__UpperCamelCase :     List[Any]										=  self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_context_encoder(*_UpperCAmelCase     )
				def 			a_			(self     )      ->			str:
							__UpperCamelCase :     int										=  self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_question_encoder(*_UpperCAmelCase     )
				def 			a_			(self     )      ->			Any:
							__UpperCamelCase :     List[Any]										=  self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_reader(*_UpperCAmelCase     )
				def 			a_			(self     )      ->			Optional[Any]:
							__UpperCamelCase :     List[Any]										=  self.model_tester.prepare_config_and_inputs()[0]

							__UpperCamelCase :     Union[str, Any]										=  DPRQuestionEncoder(config=_UpperCAmelCase     )
							model.to(_UpperCAmelCase     )
							model.eval()

							with tempfile.TemporaryDirectory() as tmp_dirname:
										model.save_pretrained(_UpperCAmelCase     )
										__UpperCamelCase :     Tuple										=  DPRQuestionEncoder.from_pretrained(_UpperCAmelCase					,    projection_dim=5_1_2     )

							self.assertIsNotNone(_UpperCAmelCase     )





				@slow
				def 			a_			(self     )      ->			Optional[Any]:
							for model_name in DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
										__UpperCamelCase :     Union[str, Any]										=  DPRContextEncoder.from_pretrained(_UpperCAmelCase     )
										self.assertIsNotNone(_UpperCAmelCase     )

							for model_name in DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
										__UpperCamelCase :     Tuple										=  DPRContextEncoder.from_pretrained(_UpperCAmelCase     )
										self.assertIsNotNone(_UpperCAmelCase     )

							for model_name in DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
										__UpperCamelCase :     Union[str, Any]										=  DPRQuestionEncoder.from_pretrained(_UpperCAmelCase     )
										self.assertIsNotNone(_UpperCAmelCase     )

							for model_name in DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
										__UpperCamelCase :     Optional[int]										=  DPRReader.from_pretrained(_UpperCAmelCase     )
										self.assertIsNotNone(_UpperCAmelCase     )







@require_torch
class    A						(					unittest.TestCase						):




				'''simple docstring'''





				@slow
				def 			a_			(self     )      ->			Dict:
							__UpperCamelCase :     int										=  DPRQuestionEncoder.from_pretrained("facebook/dpr-question_encoder-single-nq-base"					,    return_dict=_UpperCAmelCase     )
							model.to(_UpperCAmelCase     )

							__UpperCamelCase :     Optional[int]										=  torch.tensor(
							    [[1_0_1, 7_5_9_2, 1_0_1_0, 2_0_0_3, 2_0_2_6, 3_8_9_9, 1_0_1_4_0, 1_0_2_9, 1_0_2]]					,    dtype=torch.long					,    device=_UpperCAmelCase     )  # [CLS] hello, is my dog cute? [SEP]
							__UpperCamelCase :     Dict										=  model(_UpperCAmelCase     )[0]  # embedding shape = (1, 768)
							# compare the actual values for a slice.
							__UpperCamelCase :     Union[str, Any]										=  torch.tensor(
							    [
							        [
							            0.03_236_253,
							            0.12_753_335,
							            0.16_818_509,
							            0.00_279_786,
							            0.3_896_933,
							            0.24_264_945,
							            0.2_178_971,
							            -0.02_335_227,
							            -0.08_481_959,
							            -0.14_324_117,
							        ]
							    ]					,    dtype=torch.float					,    device=_UpperCAmelCase					,    )
							self.assertTrue(torch.allclose(output[:, :1_0]					,    _UpperCAmelCase					,    atol=1E-4     )     )





				@slow
				def 			a_			(self     )      ->			List[str]:
							__UpperCamelCase :     Any										=  DPRReaderTokenizer.from_pretrained("facebook/dpr-reader-single-nq-base"     )
							__UpperCamelCase :     str										=  DPRReader.from_pretrained("facebook/dpr-reader-single-nq-base"     )
							model.to(_UpperCAmelCase     )

							__UpperCamelCase :     Optional[int]										=  tokenizer(
							    questions="What is love ?"					,    titles="Haddaway"					,    texts="What Is Love is a song recorded by the artist Haddaway"					,    padding=_UpperCAmelCase					,    return_tensors="pt"					,    )
							encoded_inputs.to(_UpperCAmelCase     )

							__UpperCamelCase :     int										=  model(**_UpperCAmelCase     )

							# compare the actual values for a slice.
							__UpperCamelCase :     Dict										=  torch.tensor(
							    [[-10.3_005, -10.7_765, -11.4_872, -11.6_841, -11.9_312, -10.3_002, -9.8_544, -11.7_378, -12.0_821, -10.2_975]]					,    dtype=torch.float					,    device=_UpperCAmelCase					,    )

							__UpperCamelCase :     Optional[Any]										=  torch.tensor(
							    [[-11.0_684, -11.7_041, -11.5_397, -10.3_465, -10.8_791, -6.8_443, -11.9_959, -11.0_364, -10.0_096, -6.8_405]]					,    dtype=torch.float					,    device=_UpperCAmelCase					,    )
							self.assertTrue(torch.allclose(outputs.start_logits[:, :1_0]					,    _UpperCAmelCase					,    atol=1E-4     )     )
							self.assertTrue(torch.allclose(outputs.end_logits[:, :1_0]					,    _UpperCAmelCase					,    atol=1E-4     )     )



