



def  lowerCAmelCase_	(lowerCAmelCase__:		List[Any]		,						lowerCAmelCase__:		Tuple  ):





			"""simple docstring"""


			return (pointa[0] - pointa[0]) ** 2 + (pointa[1] - pointa[1]) ** 2







def  lowerCAmelCase_	(lowerCAmelCase__:		Optional[Any]		,						lowerCAmelCase__:		Optional[Any]=0  ):





			"""simple docstring"""


			return sorted(lowerCAmelCase__		,						key=lambda lowerCAmelCase__  : x[column]  )







def  lowerCAmelCase_	(lowerCAmelCase__:		Tuple		,						lowerCAmelCase__:		Union[str, Any]		,						lowerCAmelCase__:		int=float("""inf"""  )  ):





			"""simple docstring"""


			for i in range(points_counts - 1  ):
						for j in range(i + 1		,						lowerCAmelCase__  ):
									UpperCAmelCase_:		Tuple							      =     euclidean_distance_sqr(points[i]		,						points[j]  )
									if current_dis < min_dis:
												UpperCAmelCase_:		int							      =     current_dis
			return min_dis







def  lowerCAmelCase_	(lowerCAmelCase__:		Tuple		,						lowerCAmelCase__:		Union[str, Any]		,						lowerCAmelCase__:		List[str]=float("""inf"""  )  ):





			"""simple docstring"""


			for i in range(min(6		,						points_counts - 1  )		,						lowerCAmelCase__  ):
						for j in range(max(0		,						i - 6  )		,						lowerCAmelCase__  ):
									UpperCAmelCase_:		int							      =     euclidean_distance_sqr(points[i]		,						points[j]  )
									if current_dis < min_dis:
												UpperCAmelCase_:		Union[str, Any]							      =     current_dis
			return min_dis







def  lowerCAmelCase_	(lowerCAmelCase__:		Optional[int]		,						lowerCAmelCase__:		Tuple		,						lowerCAmelCase__:		Optional[Any]  ):





			"""simple docstring"""


			if points_counts <= 3:
						return dis_between_closest_pair(lowerCAmelCase__		,						lowerCAmelCase__  )

			# recursion
			UpperCAmelCase_:		int							      =     points_counts // 2
			UpperCAmelCase_:		str							      =     closest_pair_of_points_sqr(
			    lowerCAmelCase__		,						points_sorted_on_y[:mid]		,						lowerCAmelCase__  )
			UpperCAmelCase_:		Any							      =     closest_pair_of_points_sqr(
			    lowerCAmelCase__		,						points_sorted_on_y[mid:]		,						points_counts - mid  )
			UpperCAmelCase_:		Dict							      =     min(lowerCAmelCase__		,						lowerCAmelCase__  )
			UpperCAmelCase_:		Tuple							      =     []
			for point in points_sorted_on_x:
						if abs(point[0] - points_sorted_on_x[mid][0]  ) < closest_pair_dis:
									cross_strip.append(lowerCAmelCase__  )

			UpperCAmelCase_:		Optional[int]							      =     dis_between_closest_in_strip(
			    lowerCAmelCase__		,						len(lowerCAmelCase__  )		,						lowerCAmelCase__  )
			return min(lowerCAmelCase__		,						lowerCAmelCase__  )







def  lowerCAmelCase_	(lowerCAmelCase__:		List[Any]		,						lowerCAmelCase__:		Optional[Any]  ):





			"""simple docstring"""


			UpperCAmelCase_:		List[str]							      =     column_based_sort(lowerCAmelCase__		,						column=0  )
			UpperCAmelCase_:		int							      =     column_based_sort(lowerCAmelCase__		,						column=1  )
			return (
			    closest_pair_of_points_sqr(
			        lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__  )
			) ** 0.5


if __name__ == "__main__":
	a      :  Optional[Any]			     =			[(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
	print('Distance:', closest_pair_of_points(points, len(points)))











def  lowerCAmelCase_	(lowerCAmelCase__:		Union[str, Any]		,						lowerCAmelCase__:		Optional[int]  ):





			"""simple docstring"""


			UpperCAmelCase_:		List[str]							      =     0
			UpperCAmelCase_:		Tuple							      =     len(lowerCAmelCase__  ) - 1

			while left <= right:
						# avoid divided by 0 during interpolation
						if sorted_collection[left] == sorted_collection[right]:
									if sorted_collection[left] == item:
												return left
									else:
												return None

						UpperCAmelCase_:		Dict							      =     left + ((item - sorted_collection[left]) * (right - left)) // (
						    sorted_collection[right] - sorted_collection[left]
						)

						# out of range check
						if point < 0 or point >= len(lowerCAmelCase__  ):
									return None

						UpperCAmelCase_:		str							      =     sorted_collection[point]
						if current_item == item:
									return point
						else:
									if point < left:
												UpperCAmelCase_:		int							      =     left
												UpperCAmelCase_:		str							      =     point
									elif point > right:
												UpperCAmelCase_:		List[str]							      =     right
												UpperCAmelCase_:		Optional[int]							      =     point
									else:
												if item < current_item:
															UpperCAmelCase_:		Optional[Any]							      =     point - 1
												else:
															UpperCAmelCase_:		Any							      =     point + 1
			return None







def  lowerCAmelCase_	(lowerCAmelCase__:		Dict		,						lowerCAmelCase__:		List[Any]		,						lowerCAmelCase__:		Any		,						lowerCAmelCase__:		Any  ):





			"""simple docstring"""


			if sorted_collection[left] == sorted_collection[right]:
						if sorted_collection[left] == item:
									return left
						else:
									return None

			UpperCAmelCase_:		Union[str, Any]							      =     left + ((item - sorted_collection[left]) * (right - left)) // (
			    sorted_collection[right] - sorted_collection[left]
			)

			# out of range check
			if point < 0 or point >= len(lowerCAmelCase__  ):
						return None

			if sorted_collection[point] == item:
						return point
			elif point < left:
						return interpolation_search_by_recursion(lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__  )
			elif point > right:
						return interpolation_search_by_recursion(lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__  )
			else:
						if sorted_collection[point] > item:
									return interpolation_search_by_recursion(
									    lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__		,						point - 1  )
						else:
									return interpolation_search_by_recursion(
									    lowerCAmelCase__		,						lowerCAmelCase__		,						point + 1		,						lowerCAmelCase__  )







def  lowerCAmelCase_	(lowerCAmelCase__:		Dict  ):





			"""simple docstring"""


			if collection != sorted(lowerCAmelCase__  ):
						raise ValueError("""Collection must be ascending sorted"""  )
			return True


if __name__ == "__main__":
	import sys
	a      :  Optional[Any]			     =			0
	if debug == 1:
		a      :  int			     =			[10, 30, 40, 45, 50, 66, 77, 93]
		try:
			__assert_sorted(collection)
		except ValueError:
			sys.exit('Sequence must be ascending sorted to apply interpolation search')
		a      :  int			     =			67

	a      :  Any			     =			interpolation_search(collection, target)
	if result is not None:
		print(F'''{target} found at positions: {result}''')
	else:
		print('Not found')






