min_area.py

def minArea(x, y, k):
    # def eucledian_dist(a,b):
    #     return sqrt(sum( (a - b)**2 for a, b in zip(a, b)))
    # d = eucledian_dist(x,y)
    def avg(l):
        return sum (l) / float (len (l))

    def stats(x, y):
        x_min = min (x)
        x_max = max (x)
        y_min = min (y)
        y_max = max (y)
        return x_min, x_max, y_min, y_max

    while k < len (x):
        x_min, x_max, y_min, y_max = stats (x, y)
        if (x_max - x_min) > (y_max - y_min):
            min_idx = x.index (x_min)
        else:
            min_idx = y.index (y_min)
        del x[min_idx]
        del y[min_idx]

    x_min, x_max, y_min, y_max = stats (x, y)
    sq_xmin = x_min - 1
    sq_xmax = x_max + 1
    sq_ymin = y_min - 1
    sq_ymax = y_max + 1

    w = sq_xmax - sq_xmin
    h = sq_ymax - sq_ymin

    if w > h:
        sq_xmax += w - h
        return w ** 2
    elif h > w:
        sq_ymax += h - w
        return h ** 2
    return k

from math import sqrt
def minArea(x, y, k):
    def eucledian_dist(a,b):
        return sqrt(sum( (a - b)**2 for a, b in zip(a, b)))
    def stats(x, y):
        x_min = min (x)
        x_max = max (x)
        y_min = min (y)
        y_max = max (y)
        return x_min, x_max, y_min, y_max

    def avg(l):
        return sum(l) / float(len(l))

    def remove(x,y):
        #cluster centroids
        cx = avg(x)
        cy = avg(y)
    
        outlier_point_index = None
        outlier_point_dist = 0
        
        for idx in range(len(x)):
            dist_from_center = eucledian_dist((cx,cy), (x[idx],y[idx]))
            if outlier_point_dist < dist_from_center:
                outlier_point_index = idx
                outlier_point_dist = dist_from_center
        del x[outlier_point_index]
        del y[outlier_point_index]        
        return x,y

    while k < len (x):
        x,y = remove(x,y)        

    x_min, x_max, y_min, y_max = stats (x, y)
    sq_xmin = x_min - 1
    sq_xmax = x_max + 1
    sq_ymin = y_min - 1
    sq_ymax = y_max + 1

    w = sq_xmax - sq_xmin
    h = sq_ymax - sq_ymin

    if w > h:
        return w ** 2
    elif h > w:
        return h ** 2
    return k

x = [0,1]
y = [0,2]
k = 2
print("min ",minArea(x,y,k))

x = [-1,1,0]
y = [1,3,2]
k = 3
print("min ",minArea(x,y,k))

x = [3,1,-4]
y = [-1,-2,3]
k = 2
print("min ",minArea(x,y,k))