


'''simple docstring'''






def       _snake_case     (  )		->					list[list[int]]:
							return [list(range(1000 - i				,					-1000 - i				,					-1 ) ) for i in range(1000 )]


__UpperCAmelCase					       =							generate_large_matrix()
__UpperCAmelCase					       =							(
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)


def       _snake_case     (  A )		->					None:
							assert all(row == sorted(__lowerCAmelCase				,					reverse=__lowerCAmelCase ) for row in grid )
							assert all(list(__lowerCAmelCase ) == sorted(__lowerCAmelCase				,					reverse=__lowerCAmelCase ) for col in zip(*__lowerCAmelCase ) )


def       _snake_case     (  A )		->					int:
							lowerCAmelCase__      =			0
							lowerCAmelCase__      =			len(__lowerCAmelCase ) - 1

							# Edge cases such as no values or all numbers are negative.
							if not array or array[0] < 0:
														return 0

							while right + 1 > left:
														lowerCAmelCase__      =			(left + right) // 2
														lowerCAmelCase__      =			array[mid]

														# Num must be negative and the index must be greater than or equal to 0.
														if num < 0 and array[mid - 1] >= 0:
																					return mid

														if num >= 0:
																					lowerCAmelCase__      =			mid + 1
														else:
																					lowerCAmelCase__      =			mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
							return len(__lowerCAmelCase )


def       _snake_case     (  A )		->					int:
							lowerCAmelCase__      =			0
							lowerCAmelCase__      =			len(grid[0] )

							for i in range(len(__lowerCAmelCase ) ):
														lowerCAmelCase__      =			find_negative_index(grid[i][:bound] )
														total += bound
							return (len(__lowerCAmelCase ) * len(grid[0] )) - total


def       _snake_case     (  A )		->					int:
							return len([number for row in grid for number in row if number < 0] )


def       _snake_case     (  A )		->					int:
							lowerCAmelCase__      =			0
							for row in grid:
														for i, number in enumerate(__lowerCAmelCase ):
																					if number < 0:
																												total += len(__lowerCAmelCase ) - i
																												break
							return total


def       _snake_case     (  )		->					None:
							from timeit import timeit

							print('''Running benchmarks''' )
							lowerCAmelCase__      =			(
							    """from __main__ import count_negatives_binary_search, """
							    """count_negatives_brute_force, count_negatives_brute_force_with_break, grid"""
							)
							for func in (
							    "count_negatives_binary_search",  # took 0.7727 seconds
							    "count_negatives_brute_force_with_break",  # took 4.6505 seconds
							    "count_negatives_brute_force",  # took 12.8160 seconds
							):
														lowerCAmelCase__      =			timeit(F"""{func}(grid=grid)"""				,					setup=__lowerCAmelCase				,					number=500 )
														print(F"""{func}() took {time:0.4f} seconds""" )


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							benchmark()



'''simple docstring'''






from math import pi, sqrt, tan


def       _snake_case     (  A )		->					float:
							if side_length < 0:
														raise ValueError('''surface_area_cube() only accepts non-negative values''' )
							return 6 * side_length**2


def       _snake_case     (  A				,					A				,					A )		->					float:
							if length < 0 or breadth < 0 or height < 0:
														raise ValueError('''surface_area_cuboid() only accepts non-negative values''' )
							return 2 * ((length * breadth) + (breadth * height) + (length * height))


def       _snake_case     (  A )		->					float:
							if radius < 0:
														raise ValueError('''surface_area_sphere() only accepts non-negative values''' )
							return 4 * pi * radius**2


def       _snake_case     (  A )		->					float:
							if radius < 0:
														raise ValueError('''surface_area_hemisphere() only accepts non-negative values''' )
							return 3 * pi * radius**2


def       _snake_case     (  A				,					A )		->					float:
							if radius < 0 or height < 0:
														raise ValueError('''surface_area_cone() only accepts non-negative values''' )
							return pi * radius * (radius + (height**2 + radius**2) ** 0.5)


def       _snake_case     (  A				,					A				,					A )		->					float:
							if radius_a < 0 or radius_a < 0 or height < 0:
														raise ValueError(
														    '''surface_area_conical_frustum() only accepts non-negative values''' )
							lowerCAmelCase__      =			(height**2 + (radius_a - radius_a) ** 2) ** 0.5
							return pi * ((slant_height * (radius_a + radius_a)) + radius_a**2 + radius_a**2)


def       _snake_case     (  A				,					A )		->					float:
							if radius < 0 or height < 0:
														raise ValueError('''surface_area_cylinder() only accepts non-negative values''' )
							return 2 * pi * radius * (height + radius)


def       _snake_case     (  A				,					A )		->					float:
							if torus_radius < 0 or tube_radius < 0:
														raise ValueError('''surface_area_torus() only accepts non-negative values''' )
							if torus_radius < tube_radius:
														raise ValueError(
														    '''surface_area_torus() does not support spindle or self intersecting tori''' )
							return 4 * pow(A				,					2 ) * torus_radius * tube_radius


def       _snake_case     (  A				,					A )		->					float:
							if length < 0 or width < 0:
														raise ValueError('''area_rectangle() only accepts non-negative values''' )
							return length * width


def       _snake_case     (  A )		->					float:
							if side_length < 0:
														raise ValueError('''area_square() only accepts non-negative values''' )
							return side_length**2


def       _snake_case     (  A				,					A )		->					float:
							if base < 0 or height < 0:
														raise ValueError('''area_triangle() only accepts non-negative values''' )
							return (base * height) / 2


def       _snake_case     (  A				,					A				,					A )		->					float:
							if sidea < 0 or sidea < 0 or sidea < 0:
														raise ValueError('''area_triangle_three_sides() only accepts non-negative values''' )
							elif sidea + sidea < sidea or sidea + sidea < sidea or sidea + sidea < sidea:
														raise ValueError('''Given three sides do not form a triangle''' )
							lowerCAmelCase__      =			(sidea + sidea + sidea) / 2
							lowerCAmelCase__      =			sqrt(
							    semi_perimeter
							    * (semi_perimeter - sidea)
							    * (semi_perimeter - sidea)
							    * (semi_perimeter - sidea) )
							return area


def       _snake_case     (  A				,					A )		->					float:
							if base < 0 or height < 0:
														raise ValueError('''area_parallelogram() only accepts non-negative values''' )
							return base * height


def       _snake_case     (  A				,					A				,					A )		->					float:
							if basea < 0 or basea < 0 or height < 0:
														raise ValueError('''area_trapezium() only accepts non-negative values''' )
							return 1 / 2 * (basea + basea) * height


def       _snake_case     (  A )		->					float:
							if radius < 0:
														raise ValueError('''area_circle() only accepts non-negative values''' )
							return pi * radius**2


def       _snake_case     (  A				,					A )		->					float:
							if radius_x < 0 or radius_y < 0:
														raise ValueError('''area_ellipse() only accepts non-negative values''' )
							return pi * radius_x * radius_y


def       _snake_case     (  A				,					A )		->					float:
							if diagonal_a < 0 or diagonal_a < 0:
														raise ValueError('''area_rhombus() only accepts non-negative values''' )
							return 1 / 2 * diagonal_a * diagonal_a


def       _snake_case     (  A				,					A )		->					float:
							if not isinstance(A				,					A ) or sides < 3:
														raise ValueError(
														    '''area_reg_polygon() only accepts integers greater than or \
equal to three as number of sides''' )
							elif length < 0:
														raise ValueError(
														    '''area_reg_polygon() only accepts non-negative values as \
length of a side''' )
							return (sides * length**2) / (4 * tan(pi / sides ))
							return (sides * length**2) / (4 * tan(pi / sides ))


if __name__ == "__main__":
		import doctest

		doctest.testmod(verbose=True)  # verbose so we can see methods missing tests

		print('''[DEMO] Areas of various geometric shapes: \n''')
		print(f"""Rectangle: {area_rectangle(10, 20) = }""")
		print(f"""Square: {area_square(10) = }""")
		print(f"""Triangle: {area_triangle(10, 10) = }""")
		print(f"""Triangle: {area_triangle_three_sides(5, 12, 13) = }""")
		print(f"""Parallelogram: {area_parallelogram(10, 20) = }""")
		print(f"""Rhombus: {area_rhombus(10, 20) = }""")
		print(f"""Trapezium: {area_trapezium(10, 20, 30) = }""")
		print(f"""Circle: {area_circle(20) = }""")
		print(f"""Ellipse: {area_ellipse(10, 20) = }""")
		print('''\nSurface Areas of various geometric shapes: \n''')
		print(f"""Cube: {surface_area_cube(20) = }""")
		print(f"""Cuboid: {surface_area_cuboid(10, 20, 30) = }""")
		print(f"""Sphere: {surface_area_sphere(20) = }""")
		print(f"""Hemisphere: {surface_area_hemisphere(20) = }""")
		print(f"""Cone: {surface_area_cone(10, 20) = }""")
		print(f"""Conical Frustum: {surface_area_conical_frustum(10, 20, 30) = }""")
		print(f"""Cylinder: {surface_area_cylinder(10, 20) = }""")
		print(f"""Torus: {surface_area_torus(20, 10) = }""")
		print(f"""Equilateral Triangle: {area_reg_polygon(3, 10) = }""")
		print(f"""Square: {area_reg_polygon(4, 10) = }""")
		print(f"""Reqular Pentagon: {area_reg_polygon(5, 10) = }""")