
"""simple docstring"""



def 			_UpperCamelCase						(    _A       ,   _A   )     ->	Optional[int]:





    """simple docstring"""

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


def 			_UpperCamelCase						(    _A       ,   _A=0   )     ->	Any:





    """simple docstring"""

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


def 			_UpperCamelCase						(    _A       ,   _A       ,   _A=float("""inf"""   )   )     ->	Optional[Any]:





    """simple docstring"""

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


def 			_UpperCamelCase						(    _A       ,   _A       ,   _A=float("""inf"""   )   )     ->	str:





    """simple docstring"""

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


def 			_UpperCamelCase						(    _A       ,   _A       ,   _A   )     ->	str:





    """simple docstring"""

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

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

    _UpperCAmelCase        = dis_between_closest_in_strip(
        UpperCamelCase_       ,   len(UpperCamelCase_   )       ,   UpperCamelCase_   )
    return min(UpperCamelCase_       ,   UpperCamelCase_   )


def 			_UpperCamelCase						(    _A       ,   _A   )     ->	Optional[int]:





    """simple docstring"""

    _UpperCAmelCase        = column_based_sort(UpperCamelCase_       ,   column=0   )
    _UpperCAmelCase        = column_based_sort(UpperCamelCase_       ,   column=1   )
    return (
        closest_pair_of_points_sqr(
            UpperCamelCase_       ,   UpperCamelCase_       ,   UpperCamelCase_   )
    ) ** 0.5


if __name__ == "__main__":
 a       :						Optional[Any]       		=		[(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)))
from __future__ import annotations
class SCREAMING_SNAKE_CASE_		:







   def __init__(     self						:						Dict   ,   lowerCamelCase_						:						str   ,   lowerCamelCase_						:						str				):





    """simple docstring"""


    UpperCamelCase  ,     UpperCamelCase			  =      text, pattern
    UpperCamelCase  ,     UpperCamelCase			  =      len(lowerCamelCase_				), len(lowerCamelCase_				)







   def 						lowerCamelCase_	(     self						:						List[Any]   ,   lowerCamelCase_						:						str				):





    """simple docstring"""


    for i in range(self.patLen - 1   ,   -1   ,   -1				):
     if char == self.pattern[i]:
      return i
    return -1







   def 						lowerCamelCase_	(     self						:						Union[str, Any]   ,   lowerCamelCase_						:						int				):





    """simple docstring"""


    for i in range(self.patLen - 1   ,   -1   ,   -1				):
     if self.pattern[i] != self.text[current_pos + i]:
      return current_pos + i
    return -1







   def 						lowerCamelCase_	(     self						:						Union[str, Any]				):





    """simple docstring"""


    UpperCamelCase			  =      []
    for i in range(self.textLen - self.patLen + 1				):
     UpperCamelCase			  =      self.mismatch_in_text(lowerCamelCase_				)
     if mismatch_index == -1:
      positions.append(lowerCamelCase_				)
     else:
      UpperCamelCase			  =      self.match_in_pattern(self.text[mismatch_index]				)
      UpperCamelCase			  =      (
          mismatch_index - match_index
      )  # shifting index lgtm [py/multiple-definition]
    return positions





_SCREAMING_SNAKE_CASE 		=      """ABAABA"""
_SCREAMING_SNAKE_CASE 		=      """AB"""
_SCREAMING_SNAKE_CASE 		=      BoyerMooreSearch(text, pattern)
_SCREAMING_SNAKE_CASE 		=      bms.bad_character_heuristic()

if len(positions) == 0:
     print("""No match found""")
else:
     print("""Pattern found in following positions: """)
     print(positions)
