Problem:
 Score : 400 points    Problem Statement We have N points in a two-dimensional plane. The coordinates of the i -th point (1 \leq i \leq N) are (x_i,y_i) . Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior. Here, points on the sides of the rectangle are considered to be in the interior. Find the minimum possible area of such a rectangle.      Constraints  2 \leq K \leq N \leq 50   -10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N)   x_i≠x_j (1 \leq i<j \leq N)   y_i≠y_j (1 \leq i<j \leq N)   All input values are integers. (Added at 21:50 JST)         Input Input is given from Standard Input in the following format:  N  K  x_1  y_1  :  x_{N}  y_{N}       Output Print the minimum possible area of a rectangle that satisfies the condition.        Sample Input 1 4 4
1 4
3 3
6 2
8 1      Sample Output 1 21  One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1) , (8,1) , (1,4) and (8,4) . Its area is (8-1) × (4-1) = 21 .       Sample Input 2 4 2
0 0
1 1
2 2
3 3      Sample Output 2 1       Sample Input 3 4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999      Sample Output 3 3999999996000000001  Watch out for integer overflows.

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, XY):
    X = sorted(map(lambda x: x[0], XY))
    Y = sorted(map(lambda x: x[1], XY))

    ans = sys.maxsize
    for lx in X:
        for rx in X[::-1]:
            if lx > rx:
                break
            for by in Y:
                for ty in Y[::-1]:
                    if by > ty:
                        break

                    
                    k = 0
                    for x, y in XY:
                        if lx <= x <= rx and by <= y <= ty:
                            k += 1
                    
                    if k >= K:
                        ans = min(ans, (rx-lx)*(ty-by))
                    else:
                        break

    return ans


def main():
    N, K = read_int_n()
    XY = [read_int_n() for _ in range(N)]

    
    
    
    
    
    
    print(slv(N, K, XY))


if __name__ == '__main__':
    main()

Solution (Python):
N,K = map(int,input().split())
point = []
y_list = []

for _ in range(N):
    x,y = map(int, input().split())
    point.append((x,y))
    y_list.append(y)
point = sorted(point,key=lambda tup: tup[0])
y_list.sort()
min_area = (y_list[N-1] - y_list[0]) * (point[N-1][0] - point[0][0])

for by in range(N):
    for ty in range(by+1,N):
        size=0
        idx = [0 for _ in range(N)]
        for i in range(N):
            if (y_list[by] <= point[i][1] and y_list[ty] >= point[i][1]):
                idx[size] = i
                size +=1
        lb = 0
        while(lb + K -1 < size):
            min_area = min(min_area, (y_list[ty] - y_list[by]) * (point[idx[lb + K - 1]][0] - point[idx[lb]][0]))
            lb+=1
print(min_area)

Solution (Python):
N,K=map(int,input().split())
P= [list(map(int, input().split())) for i in range(N)]
P=sorted(P)
pi=list(enumerate(P))
minA=float("inf")
for il,xyl in pi[:N-1]:
    left=xyl[0]
    for ir,xyr in pi[il+1:]:
        right=xyr[0]
        insd=[xy_ for i,xy_ in pi if xyl[0]<=xy_[0]<=xyr[0]]
        insd=sorted(insd,key=lambda xx:xx[1])
        in_L=len(insd)
        if in_L<K:continue
        for jd in range(in_L-K+1):
            ju=jd+K-1
            down=insd[jd][1]
            upper=insd[ju][1]
            minA=min(minA,(upper-down)*(right-left))

print(minA)

Solution (Python):
N, K = [int(_) for _ in input().split()]
xy = [tuple(int(_) for _ in input().split()) for _ in range(N)]

xy.sort()

result = (10**11)**2

for i in range(N):
    xl, _ = xy[i]
    for j in range(i + 1, N):
        xh, _ = xy[j]
        ys = sorted(y for x, y in xy if xl <= x <= xh)
        if len(ys) >= K:
            d = min(ys[i + K - 1] - ys[i] for i in range(len(ys) - K + 1))
            r = d * (xh - xl)
            result = min(result, r)
print(result)

Solution (Python):
n,k = (int(i) for i in input().split())
p = [[int(i) for i in input().split()] for i in range(n)]
p,ans = sorted(p),float("inf")
q = list(enumerate(p))
for i,(a,b) in q[:n-k+1]:
	for j,(c,d) in q[i+k-1:]:
		r = sorted(y for x,y in p[i:j+1])
		r2 = r[k-1:]
		for i2,j2 in zip(r,r2):
			if i2<=b and d<=j2: ans = min(ans,(c-a)*(j2-i2))
print(ans)

Solution (Python):
import sys

N, K = map(int, input().split())
XY = sorted(list(map(int, sys.stdin.readline().split())) for i in range(N))
X, Y = [], []
for xi, yi in XY:
    X.append(xi)
    Y.append(yi)

ans = float('inf')
for i in range(N):  
    for j in range(i+1, N):  
        for k in range(N):  
            for l in range(N):  
                if Y[k] >= Y[l]:
                    continue
                cnt = 0
                for x, y in zip(X, Y):  
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        cnt += 1
                        if cnt == K:
                            ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
                            break

print(ans)

Solution (Python):
from itertools import combinations

N, K = map(int, input().split())
points = []
for i in range(N):
    points.append(list(map(int, input().split())))

points.sort(key=lambda p:p[0])


min_area = 10**20
for k in range(K, N+1):
    for l in range(0, N-k+1):
        points_tmp = points[l:l+k]
        points_tmp.sort(key=lambda p:p[1])
        for m in range(0, k-K+1):
            points_selected = points_tmp[m: m+K]
            ymin = points_selected[0][1]
            ymax = points_selected[-1][1]
            points_selected.sort(key=lambda p:p[0])
            xmin = points_selected[0][0]
            xmax = points_selected[-1][0]
            area = (xmax-xmin) * (ymax-ymin)
            min_area = min(area, min_area)

print(min_area)

Solution (Python):
from itertools import combinations

N, K = map(int, input().split())
points = []
for i in range(N):
    points.append(list(map(int, input().split())))

points.sort(key=lambda p:p[0])


min_area = 10**20
for k in range(K, N+1):
    for l in range(0, N-k+1):
        points_tmp = points[l:l+k]
        points_tmp.sort(key=lambda p:p[1])
        for m in range(0, k-K+1):
            points_selected = points_tmp[m: m+K]
            ymin = points_selected[0][1]
            ymax = points_selected[-1][1]
            points_selected.sort(key=lambda p:p[0])
            xmin = points_selected[0][0]
            xmax = points_selected[-1][0]
            area = (xmax-xmin) * (ymax-ymin)
            min_area = min(area, min_area)

print(min_area)

Solution (Python):
from itertools import combinations

N, K = map(int, input().split())
points = []
for i in range(N):
    points.append(list(map(int, input().split())))

xl = list(map(lambda p: p[0],
              points))
yl = list(map(lambda p: p[1],
              points))

def contained(point, xmin, xmax, ymin, ymax):
    return (xmin <= point[0] <= xmax) and (ymin <= point[1] <= ymax)

def count_contained(xmin, xmax, ymin, ymax):
    count = 0
    for point in points:
        if contained(point, xmin, xmax, ymin, ymax):
            count += 1
    return count

min_area = 10**20
for xs in combinations(xl, 2):
    xmin = min(xs)
    xmax = max(xs)
    for ys in combinations(yl, 2):
        ymin = min(ys)
        ymax = max(ys)
        if count_contained(xmin, xmax, ymin, ymax) >= K:
            area = (xmax-xmin) * (ymax-ymin)
            min_area = min(area, min_area)
print(min_area)

Solution (Python):
n, k = map(int, raw_input().split())
p = [map(int, raw_input().split()) for i in range(n)]
p = sorted(p, key=lambda _: _[0])
ans = 10**30
for b in range(n):
    x_b, y_b = p[b]
    for t in range(n):
        x_t, y_t = p[t]
        if y_t <= y_b:
            continue
        v = filter(lambda _: y_b <= _[1] <= y_t, p)
        for i in range(len(v) - k + 1):
            x_i, y_i = v[i]
            x_j, y_j = v[i+k-1]
            ans = min(ans, (x_j - x_i) * (y_t - y_b))
print ans

Solution (Python):
N,K=map(int,input().split())
XY=[]
for i in range(N):
  x,y=map(int,input().split())
  XY.append((x,y))
XY.sort()

ans=10**50
for i in range(N-(K-1)):
  for j in range(i+(K-1),N):
    x,y=XY[i]
    x1,y1=XY[j]
    YX=sorted(XY[i:j+1], key=lambda x:x[1])
    for k in range(len(YX)-(K-1)):
      for l in range(k+(K-1),len(YX)):
        if YX[k][1] <= y and y1 <= YX[l][1]:
          ans=min(ans,(x1-x)*(YX[l][1]-YX[k][1]))

print(ans)

Solution (Python):
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
xy_xmin = sorted(xy,key=lambda x:x[0])
ans = float("INF")
for i in range(N):
    for j in range(i+K-1,N):
        X = xy_xmin[j][0] - xy_xmin[i][0]
        xy_ymin = sorted(xy_xmin[i:j+1],key=lambda x:x[1])
        Y = float("INF")
        for k in range(0,j-i-K+2):
            Y = min(Y,xy_ymin[k+K-1][1]-xy_ymin[k][1])
        ans = min(ans,X*Y)
print(ans)

Solution (Python):
import sys
N, K = [int(x) for x in input().split()]
p = [ list(map( int, input().split()) ) for i in range(N)]
p.sort( key=lambda x:x[1])
area_min = sys.maxsize
for i in range(N):
    for j in range( i+1, N):
        xmin = min( p[i][0], p[j][0])
        xmax = max( p[i][0], p[j][0])
        tmp = [ p[x] for x in range(N) if xmin<=p[x][0]<=xmax]
        num = len(tmp)
        if num < K:
            continue
        area = sys.maxsize
        for k in range( num-K+1):
            area = min( area, abs( (xmax-xmin)*(tmp[k][1]-tmp[K-1+k][1]) ) )
            
        area_min = min( area_min, area)

print( "{}".format(area_min))

Solution (Python):
def d_axis_parallel_rectangle(N, K, P):
    x_array, y_array = [], []  
    for x, y in P:
        x_array.append(x)
        y_array.append(y)

    x_sorted = sorted(x_array)
    y_sorted = sorted(y_array)  

    
    ans = (x_sorted[N - 1] - x_sorted[0]) * (y_sorted[N - 1] - y_sorted[0])

    
    for xi in range(N):
        for xj in range(xi + 1, N):
            for yi in range(N):
                for yj in range(yi + 1, N):
                    num = 0
                    left = x_sorted[xi]
                    right = x_sorted[xj]
                    bottom = y_sorted[yi]
                    top = y_sorted[yj]

                    for i in range(N):
                        if left <= x_array[i] <= right and bottom <= y_array[i] <= top:
                            num += 1
                            if num == K:
                                ans = min(ans, (right - left) * (top - bottom))
                                break
    return ans

N,K = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(N)]
print(d_axis_parallel_rectangle(N, K, P))

Solution (Python):
import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
points_matrix = [[0]*(N+1) for i in range(N+1)]
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def count(xmin, xmax, ymin, ymax):
    num = 0
    for i in range(N):
        x,y = points[i]
        if (xmin <= x and xmax >= x) and (ymin <= y and ymax >= y):
            num += 1
    return num

for n in range(N):
    for i in range(N):
        for j in range(N):
            if points[n][0] <= to_search_x[i] and points[n][1] <= to_search_y[j]:
                points_matrix[i+1][j+1] += 1

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if (points_matrix[i][k] + points_matrix[j+1][l+1] - points_matrix[i][l+1] - points_matrix[j+1][k]) >= K:
                    ans = min(ans, (to_search_x[j]-to_search_x[i])*(to_search_y[l]-to_search_y[k]))

print(ans)

Solution (Python):
n, k = map(int,input().split())
ps = [tuple(map(int,input().split())) for i in range(n)]

sx = sorted(ps,key = lambda x: x[0]) 
nx = list(enumerate(sx)) 
ans = 5e18

for f, (x1,y1) in nx[:n-k+1]: 
    for e, (x2,y2) in nx[f+k-1:]: 
        dx = x2 - x1 
        sy = sorted(y for x,y in sx[f:e+1]) 
        for y3,y4 in zip(sy,sy[k-1:]): 
            if y3 <= y1 and y4 >= y2: 
                ans = min(ans, dx * (y4 - y3))

print(ans)

Solution (Python):
N,K = map(int,input().split())
x = [0 for i in range(N)]
y = [0 for i in range(N)]
p = [0 for i in range(N)]
q = [0 for i in range(N)]
for i in range(N):
    x[i],y[i] = map(int, input().split())
    p[i]=x[i]
    q[i]=y[i]
x.sort()
y.sort()
S = [[0 for i in range(N+1)]for i in range(N+1)]
for n in range(N):
    for i in range(N):
        for j in range(N):
            if p[n]<=x[i] and q[n]<=y[j]:
                S[i+1][j+1]+=1
R=(x[N-1]-x[0])*(y[N-1]-y[0])
for a in range(N):
    for b in range(N):
        for c in range(a,N):
            for d in range(b,N):
                if (S[a][b]+S[c+1][d+1]-S[a][d+1]-S[c+1][b])>=K:
                    if (x[c]-x[a])*(y[d]-y[b])<R:
                        R=(x[c]-x[a])*(y[d]-y[b])
print(R)

Solution (Python):
N,K = map(int,input().split())
x = [0 for i in range(N)]
y = [0 for i in range(N)]
p = [0 for i in range(N)]
q = [0 for i in range(N)]
for i in range(N):
    x[i],y[i] = map(int, input().split())
    p[i]=x[i]
    q[i]=y[i]
x.sort()
y.sort()
S = [[0 for i in range(N+1)]for i in range(N+1)]
for n in range(N):
    for i in range(N):
        for j in range(N):
            if p[n]<=x[i] and q[n]<=y[j]:
                S[i+1][j+1]+=1
R=(x[N-1]-x[0])*(y[N-1]-y[0])
for a in range(N):
    for b in range(N):
        for c in range(a,N):
            for d in range(b,N):
                if (S[a][b]+S[c+1][d+1]-S[a][d+1]-S[c+1][b])>=K:
                    if (x[c]-x[a])*(y[d]-y[b])<R:
                        R=(x[c]-x[a])*(y[d]-y[b])
print(R)

Solution (Python):
N,K = map(int,input().split())
x = [0 for i in range(N)]
y = [0 for i in range(N)]
p = [0 for i in range(N)]
q = [0 for i in range(N)]
for i in range(N):
    x[i],y[i] = map(int, input().split())
    p[i]=x[i]
    q[i]=y[i]
x.sort()
y.sort()
S = [[0 for i in range(N+1)]for i in range(N+1)]
for n in range(N):
    for i in range(N):
        for j in range(N):
            if p[n]<=x[i] and q[n]<=y[j]:
                S[i+1][j+1]+=1
R=(x[N-1]-x[0])*(y[N-1]-y[0])
for a in range(N):
    for b in range(N):
        for c in range(a,N):
            for d in range(b,N):
                if (S[a][b]+S[c+1][d+1]-S[a][d+1]-S[c+1][b])>=K:
                    if (x[c]-x[a])*(y[d]-y[b])<R:
                        R=(x[c]-x[a])*(y[d]-y[b])
print(R)

Solution (Python):
N, K = map(int, input().split())
XY = []
YX = []
for i in range(N):
    x, y = map(int, input().split())
    XY.append([x, y, i])
    YX.append([y, x, i])
XY.sort()
YX.sort()

x_order = {}
for xo, p in enumerate(XY):
    x, y, i = p
    x_order[i] = xo

cums = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N):
    y, x, pi = YX[i]
    xo = x_order[pi]
    for j in range(N + 1):
        cums[i + 1][j] = cums[i][j] + (1 if j > xo else 0)

ans = float('inf')

for i in range(N-1):
    for j in range(i+1, N):
        for k in range(N-1):
            for l in range(k+1, N):
                if cums[l+1][j+1] - cums[l+1][i] - cums[k][j+1] + cums[k][i] >= K:
                        ans = min(ans, (XY[j][0]-XY[i][0]) * (YX[l][0]-YX[k][0]))

print(ans)

Solution (Python):
def main():
    N, K = map(int, input().split())
    x, y = zip(*(
        map(int, input().split())
        for _ in range(N)
    ))

    f(N, K, x, y)


def f(N, K, x, y):
    ans = abs(max(x) - min(x)) * abs(max(y) - min(y))
    if K == N:
        print(ans)
        return

    def r(x, y, x_start=0, y_start=0):
        for xi in range(x_start, N):
            for yi in range(y_start, N):
                yield x[xi], y[yi], xi, yi

    
    
    
    
    sorted_x = sorted(x)
    sorted_y = sorted(y)
    for min_x, min_y, xi, yi in r(sorted_x, sorted_y):
        for max_x, max_y, _, _ in r(sorted_x, sorted_y, x_start=xi+1, y_start=yi+1):

            
            
            

            
            
            
            

            contains_count = 0
            for x3, y3 in zip(x, y):
                if min_x <= x3 <= max_x and min_y <= y3 <= max_y:
                    contains_count += 1
            if contains_count >= K:
                s = (max_x - min_x) * (max_y - min_y)
                ans = min(ans, s)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations as comb
N, K = map(int, input().split())
ans = (2 * 10 ** 9) ** 2 + 1
choice = min(K, 4)
xs = [0] * N
ys = [0] * N
for i in range(N):
	xs[i], ys[i] = map(int, input().split())

for idxs in comb(range(N), choice):
	x_mx = y_mx = - 10 ** 9
	x_mn = y_mn = 10 ** 9
	for i in idxs:
		x_mx = max(x_mx, xs[i])
		y_mx = max(y_mx, ys[i])
		x_mn = min(x_mn, xs[i])
		y_mn = min(y_mn, ys[i])
	in_num = sum(x_mn <= xs[i] <= x_mx and y_mn <= ys[i] <= y_mx for i in range(N))
	area = (x_mx - x_mn) * (y_mx - y_mn)
	if in_num >= K and area < ans:
		ans = area
print(ans)

Solution (Python):
n, k = map(int, input().split())
ps = [tuple(map(int, input().split())) for i in range(n)]
sx = sorted(ps)
nx = list(enumerate(sx))

ans = 5e18
for l, (x1, y1) in nx[:n - k + 1]:
    for r, (x2, y2) in nx[l + k - 1:]:
        dx = x2 - x1
        sy = sorted(y for x, y in sx[l:r + 1])
        for y3, y4 in zip(sy, sy[k - 1:]):
            if y3 <= y1 and y2 <= y4:
                ans = min(ans, dx * (y4 - y3))
print(ans)

Solution (Python):

from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = 5 * 10**18

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    if res < (r-l)*(u-d):
        continue

    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

print(res)

Solution (Python):

from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = 5 * 10**18

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if res < (r-l)*(u-d):
        continue
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue

    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

print(res)

Solution (Python):

from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = 5 * 10**18

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    if res < (r-l)*(u-d):
        continue

    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

print(res)

Solution (Python):
from itertools import combinations

def solve():
  N, K = map(int, input().split())
  vertices = [tuple(map(int, input().split())) for _ in [0]*N]
  sorted_v = sorted(vertices)
  result = float("inf")

  for l in combinations(sorted_v, min(4, K)):
    xs = sorted(x for x, y in l)
    ys = sorted(y for x, y in l)
    min_x, max_x = xs[0], xs[-1]
    min_y, max_y = ys[0], ys[-1]
    if sum(1 for x, y in vertices if min_x <= x <= max_x and min_y <= y <= max_y) >= K:
      s = (max_x - min_x) * (max_y - min_y)
      if result > s:
        result = s
  print(result)

if __name__ == "__main__":
  solve()

Solution (Python):
N,K=map(int,input().split())
X, Y, XY = [], [], []
for i in range(N):
  x, y = map(int,input().split())
  X += [x]
  Y += [y]
  XY += [[x,y]]
  
ans = float("inf")

for x1 in range(N):
  for x2 in range(x1+1,N):
    for y1 in range(N):
      for y2 in range(y1+1,N):
        boxed = 0
        for i in range(N):
          if (X[x1] - X[i])*(X[x2]-X[i])<=0 and (Y[y1] - Y[i])*(Y[y2]-Y[i])<=0:
            boxed+= 1
        if boxed >= K: 
          ans = min(ans,abs(X[x1]-X[x2])*abs(Y[y1]-Y[y2]))
          
print(ans)

Solution (Python):
import itertools
n, k = map(int, input().split())
p = []

vy = set()
vx = set()
for i in range(n):
    x, y = map(int, input().split())
    p.append((y,x))
    vy.add(y)
    vx.add(x)
vy = sorted(list(vy))
vx = sorted(list(vx))

min_area = float('inf')


for y in itertools.combinations(vy, r=2):
    for x in itertools.combinations(vx, r=2):
        cnt = 0
        for i in range(n):
            if y[0] <= p[i][0] <= y[1] and x[0] <= p[i][1] <= x[1]:
                cnt += 1
        if cnt >= k:
            min_area = min(min_area, (y[1]-y[0]) * (x[1]-x[0]))
print(min_area)

Solution (Python):
def solve():
    from itertools import combinations
    N, K = map(int, input().split())
    vertices = [tuple(map(int, input().split())) for _ in [0]*N]
    sorted_v = sorted(vertices)
    result = float("inf")
 
    for l in combinations(sorted_v, min(4, K)):
        xs = sorted(x for x, y in l)
        ys = sorted(y for x, y in l)
        min_x, max_x = xs[0], xs[-1]
        min_y, max_y = ys[0], ys[-1]
        if sum(1 for x, y in vertices if min_x <= x <= max_x and min_y <= y <= max_y) >= K:
            s = (max_x-min_x)*(max_y-min_y)
            if result > s:
                result = s
 
    print(result)
 
 
if __name__ == "__main__":
    solve()

Solution (Python):
N, K = map(int, input().split())
x = []
y = []
for i in range(N):
    xi, yi = map(int, input().split())
    x.append(xi)
    y.append(yi)
x_sorted = sorted(x)
y_sorted = sorted(y)

S_l = [[0 for i in range(N)] for j in range(N)]
S_rs = [[0 for i in range(N)] for j in range(N)]
S_ts = [[0 for i in range(N)] for j in range(N)]
S_s = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(N):
        count_l = 0
        count_rs = 0
        count_ts = 0
        count_s = 0
        for k in range(N):
            if -10 ** 9 <= x[k] <= x_sorted[i] and -10 ** 9 <= y[k] <= y_sorted[j]:
                count_l += 1
            if -10 ** 9 <= x[k] < x_sorted[i] and -10 ** 9 <= y[k] <= y_sorted[j]:
                count_rs += 1
            if -10 ** 9 <= x[k] <= x_sorted[i] and -10 ** 9 <= y[k] < y_sorted[j]:
                count_ts += 1
            if -10 ** 9 <= x[k] < x_sorted[i] and -10 ** 9 <= y[k] < y_sorted[j]:
                count_s += 1
        S_l[i][j] = count_l
        S_rs[i][j] = count_rs
        S_ts[i][j] = count_ts
        S_s[i][j] = count_s


def included(i, j, k, l):
    return S_l[j][l] - S_rs[i][l] - S_ts[j][k] + S_s[i][k]

ans = 4 * 10 ** 18
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            for l in range(k + 1, N):
                num = included(i, j, k, l)
                if num > K:
                    break
                elif num == K:
                    s = (x_sorted[j] - x_sorted[i]) * (y_sorted[l] - y_sorted[k])
                    if ans > s:
                        ans = s
                else:
                    continue
print(ans)

Solution (Python):
N,K = map(int, raw_input().split(" "))

points = []
pointsx = []
pointsy = []

smin = 0

for i in range(N):
    x,y = map(int, raw_input().split(" "))
    pointsx.append(x)
    pointsy.append(y)

spx = sorted(pointsx)

for i in range(N-K+1):
    for h in range(N-K-i+1):
        yneed = []
        for k in range(N):
            if pointsx[k]>=spx[i] and pointsx[k]<=spx[i+K+h-1]:
                yneed.append(pointsy[k])
        spy = sorted(yneed)
        ylength = 0
        xlength = spx[i+K+h-1]-spx[i]
        for k in range(len(spy) - K + 1):
            if ylength == 0: ylength = spy[k+K-1]-spy[k]
            elif ylength > spy[k+K-1]-spy[k]: ylength = spy[k+K-1]-spy[k]
        if smin == 0: smin = ylength * xlength
        elif smin > ylength * xlength:
            smin = ylength * xlength


print smin

Solution (Python):





from sys import stdin

def nPointsInRect(y0, y1, points):
  return len([p for p in points if y0 <= p[1] <= y1])

def solve(K, points):
  points.sort()  
  xs = [p[0] for p in points]          
  ys = sorted([p[1] for p in points])  
  minArea = (xs[-1] - xs[0]) * (ys[-1] - ys[0])  
  for i0 in range(len(points)):
    for i1 in range(i0 + K - 1, len(points)):
      for j in range(len(ys)):
        y0 = ys[j]
        for y1 in ys[j + K - 1:]:
          if nPointsInRect(y0, y1, points[i0 : i1 + 1]) >= K:
            area = (xs[i1] - xs[i0]) * (y1 - y0)
            minArea = min(minArea, area)
            break  
  return minArea

def splitToInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N, K = splitToInt(stdin.readline())
points = []
for i in range(N):
  x, y = splitToInt(stdin.readline())
  points.append((x, y))
print(solve(K, points))

Solution (Python):
n, k = map(int, input().split())
ps = [tuple(map(int, input().split())) for i in range(n)]

sx = sorted(ps) 
nx = list(enumerate(sx)) 
ans = 5e18

for l, (x1, y1) in nx[:n - k + 1]: 
    for r, (x2, y2) in nx[l + k - 1:]: 
        dx = x2 - x1
        sy = sorted(y for x, y in sx[l:r + 1])

        for y3, y4 in zip(sy, sy[k - 1:]):
            if y3 <= y1 and y2 <= y4:
                ans = min(ans, dx * (y4 - y3))
print(ans)

Solution (Python):
import sys
N,K=map(int,sys.stdin.readline().split())
A=sorted([int(e) for e in sys.stdin.readline().split()] for _ in range(N))
x,y=zip(*A)
Y=sorted(y)
r=(x[-1]-x[0])*(Y[-1]-Y[0])
for i in range(N):
 for j in range(i+1,N):
  for k in range(N):
   for l in range(k+1,N):
    ly=Y[k];ry=Y[l];q=(x[j]-x[i])*(ry-ly)
    if r>q and K<=(j-i+1) and K<=sum(ly<=y[z]<=ry for z in range(i,j+1)): r=q
print(r)

Solution (Python):
import sys
N,K=map(int,sys.stdin.readline().split())
A=sorted([int(e) for e in sys.stdin.readline().split()] for _ in range(N))
x,y=zip(*A)
Y=sorted(y)
r=(x[-1]-x[0])*(Y[-1]-Y[0])
for i in range(N):
 for j in range(i+1,N):
  for k in range(N):
   for l in range(k+1,N):
    ly=Y[k];ry=Y[l];q=(x[j]-x[i])*(ry-ly)
    if r>q and K<=(j-i+1) and K<=sum(ly<=y[z]<=ry for z in range(i,j+1)): r=q
print(r)

Solution (Python):
def main():
    N, K = map(int, input().split())
    XY = (tuple(map(int, input().split())) for _ in [0] * N)

    x = [0] * N
    y = [0] * N
    for i, (j, k) in enumerate(XY):
        x[i] = j
        y[i] = k

    ans = float('inf')
    for xi in range(N):
        for xj in range(N):
            if x[xi] >= x[xj]: continue
            for yi in range(N):
                for yj in range(N):
                    if y[yi] >= y[yj]: continue
                    cnt = 0
                    for i in range(N):
                        if x[xi] <= x[i] <= x[xj] and y[yi] <= y[i] <= y[yj]:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, (x[xj] - x[xi]) * (y[yj] - y[yi]))

    print(ans)

main()

Solution (Python):
from itertools import combinations as comb

def count(x1,y1,x2,y2):
    res = 0
    for x,y in point:
        if x1 <= x <= x2 and y1 <= y <= y2:
            res += 1
    return res 
    
N,K = map(int,input().split())

x = []
point = []
y_dict = {}

for i in range(N):
    a,b = map(int,input().split())
    x.append(a)
    point.append((a,b))
    y_dict[a] = b

x = sorted(x)
ans = 10**20

number = [i for i in range(N)]
C = list(comb(number,2))

for i,j in C:
    y_list = []

    for k in range(i,j+1):
        y_list.append(y_dict[x[k]])
        
    y_list = sorted(y_list)
        

    if 2 <= len(y_list):
        number2 = [i for i in range(len(y_list))]
        C_2 = list(comb(number2,2))

        for l,m in C_2:        
                x1 = x[i]
                y1 = y_list[l]
                x2 = x[j]
                y2 = y_list[m]
                n = count(x1,y1,x2,y2)
                   
                if K <= n :
                    ans = min(ans,(x2-x1)*(y2-y1)) 
               
print(ans)

Solution (Python):
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
pts=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	y.append(a2)
	pts.append([a1,a2])


x.sort()
y.sort()





pts.sort(key=lambda x:x[0])


ans=10**20


for y1 in y:
	for y2 in y:
		if y1>=y2:
			continue
		for x1 in x:
			cnt=0
			for p in pts:
				if p[0]>=x1 and p[1]>=y1 and p[1]<=y2:
					
					cnt+=1
					if cnt==K:
						x2=p[0]
						
						ans=min(ans,abs(x2-x1)*abs(y2-y1))
						break

print ans

Solution (Python):
n, k = map(int, input().split())
ps = [tuple(map(int, input().split())) for i in range(n)]
sx = sorted(ps)
nx = list(enumerate(sx))

ans = 5e18
for l, (x1, y1) in nx[:n - k + 1]:
    for r, (x2, y2) in nx[l + k - 1:]:
        dx = x2 - x1
        sy = sorted(y for x, y in sx[l:r + 1])
        for y3, y4 in zip(sy, sy[k - 1:]):
            if y3 <= y1 and y2 <= y4:
                ans = min(ans, dx * (y4 - y3))
print(ans)

Solution (Python):
N,K = map(int, input().split())
p = []
for i in range(N):
    a,b = map(int, input().split())
    p.append((a,b))
    
sx = sorted(p)
ans = 10**50
for x1,y1 in sx:
    for x2,y2 in sx:
        if x2 <= x1:
            continue
        l = sx.index((x1, y1))
        r = sx.index((x2, y2))
        if r-l+1 < K:
            continue
        sy = sorted(sx[l:r+1],key=lambda coor: coor[1])
        for j in range(len(sy)-K+1):
            if sy[j][1] <= y1 and y2 <= sy[j+K-1][1]:
                ans = min(ans, (x2 - x1) * (sy[j+K-1][1]-sy[j][1])) 
print(ans)