import sys
import math

def dist(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

def brute_force(points):
    min_val = float('inf')
    p1, p2 = None, None
    n = len(points)
    for i in range(n):
        for j in range(i + 1, n):
            d = dist(points[i], points[j])
            if d < min_val:
                min_val = d
                p1, p2 = points[i], points[j]
    return p1, p2, min_val

def strip_closest(strip, size, d, best_pair):
    min_val = d
    strip.sort(key=lambda point: point[1])
    
    for i in range(size):
        for j in range(i + 1, size):
            if (strip[j][1] - strip[i][1]) >= min_val:
                break
            d_curr = dist(strip[i], strip[j])
            if d_curr < min_val:
                min_val = d_curr
                best_pair = (strip[i], strip[j])
                
    return best_pair, min_val

def recursive_closest(points_sorted_x):
    n = len(points_sorted_x)
    if n <= 3:
        return brute_force(points_sorted_x)

    mid = n // 2
    mid_point = points_sorted_x[mid]

    p1_l, p2_l, dl = recursive_closest(points_sorted_x[:mid])
    p1_r, p2_r, dr = recursive_closest(points_sorted_x[mid:])

    if dl < dr:
        d = dl
        best_pair = (p1_l, p2_l)
    else:
        d = dr
        best_pair = (p1_r, p2_r)

    strip = []
    for i in range(n):
        if abs(points_sorted_x[i][0] - mid_point[0]) < d:
            strip.append(points_sorted_x[i])

    strip_pair, strip_d = strip_closest(strip, len(strip), d, best_pair)

    if strip_d < d:
        return strip_pair[0], strip_pair[1], strip_d
    else:
        return best_pair[0], best_pair[1], d

def solve():
    points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10)]
    print("Input: ", end="")
    print(points)

    points.sort(key=lambda x: x[0])
    
    p1, p2, min_d = recursive_closest(points)
    
    print(f"Closest Pair = {p1} and {p2}")
    print(f"Minimum Distance = {round(min_d, 2)}")

if __name__ == "__main__":
    solve()