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 sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
 
N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b))
sx = sorted(p)
ans = 10**50
for x,y in sx:
    for x2,y2 in sx:
        if x2 <= x:
            continue
        points = sx.index((x2,y2)) - sx.index((x,y)) + 1
        if points < K:
            continue
        sy = sorted(sx[sx.index((x,y)):sx.index((x2,y2))+1],key=lambda coor: coor[1])
        for j in range(len(sy)-K, -1, -1):
            if sy[j][1] <= y and y2 <= sy[j+K-1][1]:
                ans = min(ans, (x2 - x) * (sy[j+K-1][1]-sy[j][1])) 
print(ans)

Solution (Python):
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
 
N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b))
sx = sorted(p)
ans = 10**50
for x,y in sx:
    for x2,y2 in sx:
        if x2 <= x:
            continue
        points = sx.index((x2,y2)) - sx.index((x,y)) + 1
        if points < K:
            continue
        sy = sorted(sx[sx.index((x,y)):sx.index((x2,y2))+1],key=lambda sx: sx[1])
        for j in range(len(sy)-K+1):
            if sy[j][1] <= y and y2 <= sy[j+K-1][1]:
                ans = min(ans, (x2 - x) * (sy[j+K-1][1]-sy[j][1])) 
print(ans)

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

xs = []
ys = []
for i in range(N):
    x,y = map(int,input().split())
    xs.append((x,y,i))
    ys.append((y,x,i))
xs.sort()
ys.sort()

x_order = {}
for xo,p in enumerate(xs):
    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 = ys[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 x1 in range(N-1):
    for x2 in range(x1+1,N):
        for y1 in range(N-1):
            for y2 in range(y1+1,N):
                if cums[y2+1][x2+1] - cums[y2+1][x1] - cums[y1][x2+1] + cums[y1][x1] < K:
                    continue
                area = (xs[x2][0] - xs[x1][0]) * (ys[y2][0] - ys[y1][0])
                ans = min(ans, area)
print(ans)

Solution (Python):
N, K = map(int, input().split())
points = [tuple(map(int, input().split())) for i in range(N)]

ptsX = sorted(points, key=lambda t: t[0])
ptsY = sorted(points, key=lambda t: t[1])

ans = float('inf')
for iLeft, ptLeft in enumerate(ptsX):
    setX = set(ptsX[iLeft:])

    for ptRight in ptsX[iLeft + 1:][::-1]:
        if len(setX) < K: break
        lenX = ptRight[0] - ptLeft[0]

        for iBottom, ptBottom in enumerate(ptsY):
            setY = set(ptsY[iBottom:])

            for ptTop in ptsY[iBottom + 1:][::-1]:
                if len(setY) < K: break

                num = len(setX & setY)
                if num < K: break

                if num == K:
                    lenY = ptTop[1] - ptBottom[1]
                    area = lenX * lenY
                    ans = min(ans, area)

                setY.remove(ptTop)

        setX.remove(ptRight)

print(ans)

Solution (Python):
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]

N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b,i))
sx = sorted(p)
ans = 10**50
for x,y,i in sx:
    for x2,y2,i2 in sx:
        if x2 <= x:
            continue
        points = sx.index((x2,y2,i2)) - sx.index((x,y,i)) + 1
        if points < K:
            continue
        sy = sorted(sx[sx.index((x,y,i)):sx.index((x2,y2,i2))+1],key=lambda sx: sx[1])
        for j in range(len(sy)-K+1):
            if sy[j][1] <= y and y2 <= sy[j+K-1][1]:
                ans = min(ans, (x2 - x) * (sy[j+K-1][1]-sy[j][1])) 
print(ans)

Solution (Python):
import math,heapq,collections,sys,numpy
sys.setrecursionlimit(10**7)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b,i))
sx = sorted(p)
ans = 10**50
for x,y,i in sx:
    for x2,y2,i2 in sx:
        if x2 <= x:
            continue
        points = sx.index((x2,y2,i2)) - sx.index((x,y,i)) + 1
        if points >= K:
            sy2 = sorted(sx[sx.index((x,y,i)):sx.index((x2,y2,i2))+1],key=lambda sx: sx[1])
            for j in range(len(sy2)-K+1):
                if sy2[j][1] <= y and sy2[j+K-1][1] >= y2:          
                    ans = min(ans, (x2 - x) * (sy2[j+K-1][1]-sy2[j][1])) 
print(ans)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,k]=i2()
x=[]
y=[]
zz=[]
for i in range(n):
 z=i2()
 x.append([z[0],i])
 y.append([z[1],i])
 zz.append(z)
x.sort()
y.sort()
xx=[i[1] for i in x]
yy=[i[1] for i in y]
a=float("inf")
for i in range(n):
 for j in range(i,n):
  for kk in range(n):
   for l in range(kk,n):
     if len(set(xx[i:j+1])&set(yy[kk:l+1]))==k:
         a=min(a,(zz[xx[j]][0]-zz[xx[i]][0])*(zz[yy[l]][1]-zz[yy[kk]][1]))
print(a)

Solution (Python):
def D_Axis_Parallel_Rectangle(N, K, P):
    x = [0 for _ in range(N)]  
    y = [0 for _ in range(N)]  
    x_array = [0 for _ in range(N)]
    y_array = [0 for _ in range(N)]
    for i in range(N):
        x[i] = P[i][0]
        y[i] = P[i][1]
        x_array[i] = x[i]
        y_array[i] = y[i]

    x_array = sorted(x_array)
    y_array = sorted(y_array)

    
    ans = (x_array[N - 1] - x_array[0]) * (y_array[N - 1] - y_array[0])

    
    for xi in range(0, N, 1):
        for xj in range(xi + 1, N, 1):
            for yi in range(0, N, 1):
                for yj in range(yi + 1, N, 1):
                    num = 0
                    left = x_array[xi]
                    right = x_array[xj]
                    bottom = y_array[yi]
                    upper = y_array[yj]

                    for i in range(N):
                        if(left <= x[i] and x[i] <= right and bottom <= y[i] and y[i] <= upper):
                            num += 1
                    if num >= K:
                        ans = min(ans, (right - left) * (upper - bottom))
    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):
n, k = map(int, input().split())
sx, sy = [], []
for i in range(n):
    x, y = map(int, input().split())
    sx.append((x, i))
    sy.append((y, i))
sx.sort()
sy.sort()
px = [[0] for _ in range(n)]
for cx, (x, i) in enumerate(sx):
    px[i] = cx

acm = [[0] * (n + 1) for _ in range(n + 1)]
for cy, (y, i) in enumerate(sy):
    for cx in range(n):
        acm[cx][cy] = acm[cx - 1][cy] + acm[cx][cy - 1] - acm[cx - 1][cy - 1] + int(px[i] == cx)

ans = 5e18
for lcx in range(n - k + 1):
    for lcy in range(n - k + 1):
        acm_l = acm[lcx - 1][lcy - 1]
        for ucx in range(lcx + k - 1, n):
            for ucy in range(lcy + k - 1, n):
                if acm[ucx][ucy] - acm[ucx][lcy - 1] - acm[lcx - 1][ucy] + acm_l >= k:
                    ans = min(ans, (sx[ucx][0] - sx[lcx][0]) * (sy[ucy][0] - sy[lcy][0]))
                    break
print(ans)

Solution (Python):
n, k = map(int, input().split())
sx, sy = [], []
for i in range(n):
    x, y = map(int, input().split())
    sx.append((x, i))
    sy.append((y, i))
sx.sort()
sy.sort()
px = [[0] for _ in range(n)]
for cx, (x, i) in enumerate(sx):
    px[i] = cx

acm = [[0] * (n + 1) for _ in range(n + 1)]
for cy, (y, i) in enumerate(sy):
    for cx in range(n):
        acm[cx][cy] = acm[cx - 1][cy] + acm[cx][cy - 1] - acm[cx - 1][cy - 1] + int(px[i] == cx)

ans = 5e18
for lcx in range(n - k + 1):
    for ucx in range(lcx + k - 1, n):
        for lcy in range(n - k + 1):
            for ucy in range(lcy + k - 1, n):
                
                
                if acm[ucx][ucy] - acm[ucx][lcy - 1] - acm[lcx - 1][ucy] + acm[lcx - 1][lcy - 1] >= k:
                    ans = min(ans, (sx[ucx][0] - sx[lcx][0]) * (sy[ucy][0] - sy[lcy][0]))
print(ans)

Solution (Python):
from collections import defaultdict, Counter
from itertools import combinations
INF = float("inf")


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

    ans = INF
    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    y1, y2, x1, x2 = points[i][0], points[j][0], points[k][1], points[l][1]
                    area = abs(y1 - y2) * abs(x1 - x2)
                    if y1 <= y2 and x1 <= x2 and area < ans:
                        n = 0
                        for p in points:
                            n += y1 <= p[0] <= y2 and x1 <= p[1] <= x2
                        if n >= K:
                            ans = min(ans, area)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, raw_input().split())
ps = []
for i in xrange(N):
  ps.append(map(int, raw_input().split()))

xsorted = zip(*sorted(ps, key=lambda p: p[0]))[0]
ysorted = zip(*sorted(ps, key=lambda p: p[1]))[1]

ans = float('inf')
for i in xrange(N):
  bottom = ysorted[i]
  for j in xrange(i+K-1, N):
    top = ysorted[j]
    for k in xrange(N):
      if k+K-1 >= N:
        break
      right = xsorted[k]
      
      f, t = k+K-1, N
      sol = None
      while True:
        mid = (f+t)//2
        left = xsorted[mid]
        c = 0
        for p in ps:
          if right <= p[0] <= left and bottom <= p[1] <= top:
            c += 1
            if c >= K: break
        else:
          if f+1 >= t:
            break
          f = mid
          continue
        sol = mid
        if f+1 >= t:
          break
        t = mid
      if sol:
        area = (xsorted[sol] - right) * (top - bottom)
        if area < ans:
          ans = area

print ans

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

xDict = {}
index = 0
for x,y in points1:
	if index in xDict:
		if xDict[index] != x:
			index += 1
			xDict[index] = x
	else:
		xDict[index] = x

yDict = {}
index = 0
for y in points2:
	if index in yDict:
		if yDict[index] != y:
			index += 1 
			yDict[index] = y
	else:
		yDict[index] = y

nPoints = [[0 for j in range(len(yDict))] for i in range(len(xDict))]

for kx,vx in xDict.items():
	for ky,vy in yDict.items():
		exists = 1 if (vx,vy) in points1 else 0
		if kx == 0 and ky == 0:
			nPoints[kx][ky] += exists
		elif kx == 0 and ky > 0:
			nPoints[kx][ky] += nPoints[kx][ky-1] + exists
		elif kx > 0 and ky == 0:
			nPoints[kx][ky] += nPoints[kx-1][ky] + exists
		else:
			nPoints[kx][ky] += nPoints[kx-1][ky] + nPoints[kx][ky-1] - nPoints[kx-1][ky-1] + exists

ans = -1
for x1 in range(len(xDict)):
	for x2 in range(x1+1,-1,-1):
		for y1 in range(len(yDict)):
			for y2 in range(y1+1,-1,-1):
				point = nPoints[x1][y1]
				if x2 > 0:
					point -= nPoints[x2-1][y1]
				if y2 > 0:
					point -= nPoints[x1][y2-1]
				if x2 > 0 and y2 > 0:
					point += nPoints[x2-1][y2-1]
				if point >= K:
					area = (xDict[x1]-xDict[x2]) * (yDict[y1]-yDict[y2])
					if ans < 0:
						ans = area
					else:
						ans = min(ans, area)
					break
print(ans)

Solution (Python):

import numpy as np

N, K = map(int, input().split())
x_list = []
y_list = []

for _ in range(N):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

x_list_np = np.array(x_list)
x_args = np.argsort(x_list_np)
x_sorted = np.sort(x_list_np)

res = (max(x_list) - min(x_list)) * (max(y_list) - min(y_list))

for i1 in range(N):
    for i2 in range(i1+K-1, N):
        x_ = x_sorted[i2] - x_sorted[i1]
        y_pick = np.sort(np.array(y_list)[x_args[i1:(i2+1)]])
        y_ = min([y_pick[i+K-1] - y_pick[i] for i in range(i2-i1-K+2)])
        res = min(res, x_*y_)
print(res)

Solution (Python):
from collections import defaultdict, Counter
from itertools import combinations
INF = float("inf")


memo1 = {}
memo2 = {}

def ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K):
    if (y1, y2) in memo1:
        y = memo1[(y1, y2)]
    else:
        a = yd2[y1]
        b = yd[y2]
        y = b.difference(a)
        memo1[(y1, y2)] = y

    if (x1, x2) in memo2:
        x = memo2[(x1, x2)]
    else:
        c = xd2[x1]
        d = xd[x2]
        x = d.difference(c)
        memo2[(x1, x2)] = x

    
    

    n = len(y & x)

    return n >= K


def main():
    import time
    N, K = map(int, raw_input().split())
    ys, xs = [], []
    for i in range(N):
        x, y = map(int, raw_input().split())
        ys.append((y, i))
        xs.append((x, i))

    ys.sort()
    yd = defaultdict(set)
    yd2 = defaultdict(set)
    old = set()
    for y, i in ys:
        yd2[y] = old.copy()
        old.add(i)
        yd[y] = old.copy()

    xs.sort()
    xd = defaultdict(set)
    xd2 = defaultdict(set)
    old = set()
    for x, i in xs:
        xd2[x] = old.copy()
        old.add(i)
        xd[x] = old.copy()

    ans = INF

    
    
    
    
    for i, j in combinations(range(N), 2):
        for k, l in combinations(range(N), 2):
            a, b, c, d = ys[i], ys[j], xs[k], xs[l]
            y1 = min(a[0], b[0])
            y2 = max(a[0], b[0])

            x1 = min(c[0], d[0])
            x2 = max(c[0], d[0])

            kkk = abs(x1 - x2) * abs(y1 - y2)
            if kkk < ans:
                
                
                
                
                if ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K):
                    ans = kkk

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n,K = map(int,input().split())

x,y = [],[]
xx,yy = [],[]

for _ in range(n):
    X,Y = map(int,input().split())

    x.append(X)
    xx.append(X)
    y.append(Y)
    yy.append(Y)

xx.sort()
yy.sort()

ans = 10**20
for i in range(n):
    for j in range(i):
        lx,rx = xx[j],xx[i]

        num = [0 for _ in range(n+1)]
        for k in range(n):
            if lx <= x[k] <= rx:
                num[yy.index(y[k])+1] += 1

        for k in range(n):
            num[k+1] += num[k]

        for k in range(n):
            for l in range(k):
                ly,ry = yy[l],yy[k]

                if num[k+1] - num[l] >= K:
                    ans = min(ans, (rx-lx)*(ry-ly))

print(ans)

Solution (Python):
n,K = map(int,input().split())

x,y = [],[]
xx,yy = [],[]

for _ in range(n):
    X,Y = map(int,input().split())

    x.append(X)
    xx.append(X)
    y.append(Y)
    yy.append(Y)

xx.sort()
yy.sort()

ans = 10**20
for i in range(n):
    for j in range(i):
        lx,rx = xx[j],xx[i]

        num = [0 for _ in range(n+1)]
        for k in range(n):
            if lx <= x[k] <= rx:
                num[yy.index(y[k])+1] += 1

        for k in range(n):
            num[k+1] += num[k]

        for k in range(n):
            for l in range(k):
                ly,ry = yy[l],yy[k]

                if num[k+1] - num[l] >= K:
                    ans = min(ans, (rx-lx)*(ry-ly))

print(ans)

Solution (Python):
(n, k) = map(int, input().split(" "))

xs = []
ys = []
pts = []
for _ in range(n):
    (x, y) = map(int, input().split(" "))
    xs += [x]
    ys += [y]
    pts += [(x, y)]

xs.sort()
ys.sort()

res = float("inf")
for a in xs:
    for b in xs:
        ci = 0
        di = 1
        while di < len(ys):
            num = 0
            c = ys[ci]
            d = ys[di]
            
            for x in pts:
                if a <= x[0] <= b and c <= x[1] <= d:
                    num += 1
        
            if num >= k:
                res = min(res, abs(b-a)*abs(d-c))
                if ci < di:
                    ci += 1
                else:
                    di += 1
            else:
                di += 1

print(res)

Solution (Python):


n,k=[int(x) for x in input().split()]
x=[0]*n
y=[0]*n
for i in range(n):
   x[i],y[i]=[int(x) for x in input().split()]
from itertools import product
ans=float("inf")
for xmax,xmin,ymax,ymin in product(x,x,y,y):
    if xmax<=xmin or ymax<=ymin or (xmax-xmin)*(ymax-ymin)>=ans:
        continue
    if len([0 for xi,yi in zip(x,y) if xmin<=xi<=xmax and ymin<=yi<=ymax])>=k:
        ans=(xmax-xmin)*(ymax-ymin)
print(ans)

Solution (Python):


import itertools


def det_rect_area(n, k, points):
    area = float("inf")
    
    xs = (p[0] for p in points)
    ys = (p[1] for p in points)
    all_points = itertools.product(xs, ys)
    for (x1, y1), (x2, y2) in itertools.combinations(all_points, 2):
        min_x, max_x = min(x1, x2), max(x1, x2)
        min_y, max_y = min(y1, y2), max(y1, y2)
        
        num_inc_rects = 0
        for x, y in points:
            if min_x <= x <= max_x and min_y <= y <= max_y:
                num_inc_rects += 1
        if num_inc_rects >= k:
            area = min(area, (max_x - min_x) * (max_y - min_y))
    return area


def main():
    n, k = (int(x) for x in input().split())
    points = [tuple(int(x) for x in input().split()) for _ in range(n)]
    print(det_rect_area(n, k, points))


if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
p=[]
for i in range(n):
    x,y=map(int,input().split())
    p.append([x,y])
ret=10**25
for a in range(n):
    for b in range(a):
        r=max(p[a][0],p[b][0])
        l=min(p[a][0],p[b][0])
        for c in range(n):
            for d in range(c):
                u=min(p[c][1],p[d][1])
                t=max(p[c][1],p[d][1])
                cnt=0
                for i in range(n):
                    if l<=p[i][0]<=r and u<=p[i][1]<=t:
                        cnt+=1
                if cnt>=k:
                    ret=min(ret,(r-l)*(t-u))
print(ret)

Solution (Python):
line=input().split()
n=int(line[0])
k=int(line[1])

points=[]
hojds=[]
bredds=[]
for i in range(n):
    line=input().split()
    x=int(line[0])
    y=int(line[1])
    points.append([x,y])
    bredds.append(x)
    hojds.append(y)
hojds.sort()
bredds.sort()
points.sort(key=lambda x:x[0])

area=10**18*4
for h1 in hojds:
    for h2 in hojds:
        if h1>=h2:
            continue
        for b1 in bredds:
            num=0
            for p in points:
                if p[0]>=b1 and p[1]>=h1 and p[1]<=h2:
                    num+=1
                    if num==k:
                        b2=p[0]
                        newarea=(b2-b1)*(h2-h1)
                        area=min(area,newarea)
                        break
            
print(area)

Solution (Python):
n, k = map(int, input().split())
xys = [tuple(map(int, input().split())) for _ in range(n)]
x = list(sorted([xy[0] for xy in xys]))
y = list(sorted([xy[1] for xy in xys]))

ans = int(4e18)
for i0 in range(len(x) - 1):
    x0 = x[i0]
    for i1 in range(i0 + 1, len(x)):
        x1 = x[i1]
        for j0 in range(len(y) - 1):
            y0 = y[j0]
            for j1 in range(j0 + 1, len(y)):
                y1 = y[j1]
                s = (x1 - x0) * (y1 - y0)
                cnt = 0
                for xy in xys:
                    if x0 <= xy[0] <= x1 and y0 <= xy[1] <= y1:
                        cnt += 1
                if k <= cnt:
                    ans = min(ans, s)
print(ans)

Solution (Python):
n, k = map(int, input().split())
X = set(); Y = set()
P = set()
for i in range(n):
    x, y = map(int, input().split())
    X.add(x); Y.add(y)
    P.add((x, y))

X = sorted(X); w = len(X)
Y = sorted(Y); h = len(Y)
MX = {x: i for i, x in enumerate(X)}
MY = {y: i for i, y in enumerate(Y)}
Q = {(MX[x], MY[y]) for x, y in P}
S = [[0]*(w+1) for i in range(h+1)]
for i in range(h):
    tmp = 0
    for j in range(w):
        if (j, i) in Q:
            tmp += 1
        S[i+1][j+1] = S[i][j+1] + tmp

ans = 10**100
for y1 in range(h):
    for x1 in range(w):
        for y2 in range(h):
            for x2 in range(w):
                count = S[y2+1][x2+1] - S[y2+1][x1] - S[y1][x2+1] + S[y1][x1]
                if count >= k:
                    ans = min(ans, (X[x2]-X[x1])*(Y[y2]-Y[y1]))
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,k = LI()
    xs = set()
    ys = set()
    a = []
    for _ in range(n):
        x,y = LI_()
        a.append((x,y))
        xs.add(x)
        ys.add(y)
    xd = {}
    yd = {}
    for x,i in zip(sorted(list(xs)), range(n)):
        xd[x] = i
    for y,i in zip(sorted(list(ys)), range(n)):
        yd[y] = i
    xis = sorted(list(xs))
    yis = sorted(list(ys))

    b = []
    for x,y in a:
        b.append((xd[x],yd[y]))

    if k == 1:
        return 0

    r = inf
    for i in range(n):
        xi = xis[i]
        for j in range(n-1,i-1,-1):
            xj = xis[j]
            xf = True
            for l in range(n):
                yl = yis[l]
                for m in range(n-1,l-1,-1):
                    t = 0
                    for x,y in b:
                        if i <= x <= j and l <= y <= m:
                            t += 1
                    if t >= k:
                        tr = (xj-xi) * (yis[m]-yl)
                        if tr < r:
                            r = tr
                        xf = False
                    else:
                        break
            if xf:
                break

    return r


print(main())

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, kk = na()
ps = [na() for _ in range(n)]

ans = 99999999999999999999999
for i in range(n):
    for j in range(n):
        for k in range(n):
            for l in range(n):
                if ps[i][0] <= ps[k][0] and ps[j][1] <= ps[l][1] and (ps[k][0]-ps[i][0])*(ps[l][1]-ps[j][1]) < ans:
                    hit = len([_ for _ in ps if ps[i][0] <= _[0] <= ps[k][0] and ps[j][1] <= _[1] <= ps[l][1]])
                    if hit >= kk:
                        ans = (ps[k][0]-ps[i][0])*(ps[l][1]-ps[j][1])
print(ans)