


"""simple docstring"""







def    UpperCAmelCase__       (lowerCAmelCase_  ,						lowerCAmelCase_   ):




					'''simple docstring'''


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




def    UpperCAmelCase__       (lowerCAmelCase_  ,						lowerCAmelCase_=0   ):




					'''simple docstring'''


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




def    UpperCAmelCase__       (lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_=float("inf"   )   ):




					'''simple docstring'''


					for i in range(points_counts - 1   ):
										for j in range(i + 1  ,						lowerCAmelCase_   ):
															__SCREAMING_SNAKE_CASE						   =				euclidean_distance_sqr(points[i]  ,						points[j]   )
															if current_dis < min_dis:
																				__SCREAMING_SNAKE_CASE						   =				current_dis
					return min_dis




def    UpperCAmelCase__       (lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_=float("inf"   )   ):




					'''simple docstring'''


					for i in range(min(6  ,						points_counts - 1   )  ,						lowerCAmelCase_   ):
										for j in range(max(0  ,						i - 6   )  ,						lowerCAmelCase_   ):
															__SCREAMING_SNAKE_CASE						   =				euclidean_distance_sqr(points[i]  ,						points[j]   )
															if current_dis < min_dis:
																				__SCREAMING_SNAKE_CASE						   =				current_dis
					return min_dis




def    UpperCAmelCase__       (lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_   ):




					'''simple docstring'''


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

					# recursion
					__SCREAMING_SNAKE_CASE						   =				points_counts // 2
					__SCREAMING_SNAKE_CASE						   =				closest_pair_of_points_sqr(
					    lowerCAmelCase_  ,						points_sorted_on_y[:mid]  ,						lowerCAmelCase_   )
					__SCREAMING_SNAKE_CASE						   =				closest_pair_of_points_sqr(
					    lowerCAmelCase_  ,						points_sorted_on_y[mid:]  ,						points_counts - mid   )
					__SCREAMING_SNAKE_CASE						   =				min(lowerCAmelCase_  ,						lowerCAmelCase_   )
					__SCREAMING_SNAKE_CASE						   =				[]
					for point in points_sorted_on_x:
										if abs(point[0] - points_sorted_on_x[mid][0]   ) < closest_pair_dis:
															cross_strip.append(lowerCAmelCase_   )

					__SCREAMING_SNAKE_CASE						   =				dis_between_closest_in_strip(
					    lowerCAmelCase_  ,						len(lowerCAmelCase_   )  ,						lowerCAmelCase_   )
					return min(lowerCAmelCase_  ,						lowerCAmelCase_   )




def    UpperCAmelCase__       (lowerCAmelCase_  ,						lowerCAmelCase_   ):




					'''simple docstring'''


					__SCREAMING_SNAKE_CASE						   =				column_based_sort(lowerCAmelCase_  ,						column=0   )
					__SCREAMING_SNAKE_CASE						   =				column_based_sort(lowerCAmelCase_  ,						column=1   )
					return (
					    closest_pair_of_points_sqr(
					        lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_   )
					) ** 0.5


if __name__ == "__main__":
		a__				:							List[str]						=     [(2, 3), (1_2, 3_0), (4_0, 5_0), (5, 1), (1_2, 1_0), (3, 4)]
		print('''Distance:''', closest_pair_of_points(points, len(points)))




"""simple docstring"""







def    UpperCAmelCase__       (lowerCAmelCase_   ):




					'''simple docstring'''


					if upper_limit < 0:
										raise ValueError("Limit for the Catalan sequence must be ≥ 0"   )

					__SCREAMING_SNAKE_CASE						   =				[0] * (upper_limit + 1)

					# Base case: C(0) = C(1) = 1
					__SCREAMING_SNAKE_CASE						   =				1
					if upper_limit > 0:
										__SCREAMING_SNAKE_CASE						   =				1

					# Recurrence relation: C(i) = sum(C(j).C(i-j-1)), from j = 0 to i
					for i in range(2  ,						upper_limit + 1   ):
										for j in range(lowerCAmelCase_   ):
															catalan_list[i] += catalan_list[j] * catalan_list[i - j - 1]

					return catalan_list


if __name__ == "__main__":
		print('''\n********* Catalan Numbers Using Dynamic Programming ************\n''')
		print('''\n*** Enter -1 at any time to quit ***''')
		print('''\nEnter the upper limit (≥ 0) for the Catalan number sequence: ''', end='''''')
		try:
				while True:
						a__				:							List[str]						=     int(input().strip())
						if N < 0:
								print('''\n********* Goodbye!! ************''')
								break
						else:
								print(F"The Catalan numbers from 0 through {N} are:")
								print(catalan_numbers(N))
								print('''Try another upper limit for the sequence: ''', end='''''')
		except (NameError, ValueError):
				print('''\n********* Invalid input, goodbye! ************\n''')

		import doctest

		doctest.testmod()
