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):
def solve():
    res = float('inf')
    for i in range(n):
        r_top = coordinates[i][1]
        for j in range(n):
            r_bottom = coordinates[j][1]
            if r_bottom < r_top:
                continue
            for k in range(n):
                c_left = coordinates[k][0]
                for l in range(n):
                    c_right = coordinates[l][0]
                    if c_right < c_left:
                        continue
                    cnt = 0
                    for c, r in coordinates:
                        
                        if (r_top <= r <= r_bottom) and (c_left <= c <= c_right):
                            cnt += 1
                            if cnt >= need:
                                res = min(res, (r_bottom - r_top) * (c_right - c_left))
                                break

    return res


n, need = map(int, input().split())
coordinates = tuple(sorted(tuple(map(int, input().split())) for _ in range(n)))




print(solve())

Solution (Python):
import sys
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N,K = inputs()
xy = [inputs() for _ in range(N)]

xy = sorted(xy,key=lambda x: x[0])

ans = 10**20
for i in range(N-K+1):
  for j in range(i+K-1,N):
    
    xy1 = xy[i:j+1]
    
    xy1 = sorted(xy1,key=lambda x: x[1])
    mi = min(xy1[i+K-1][1]-xy1[i][1] for i in range(len(xy1)-K+1))
    ans = min(ans,(xy[j][0]-xy[i][0])*mi)
print(ans)

Solution (Python):
if __name__ == "__main__":
    INF = 40 ** 18 + 1
    N, K = map(int, input().split())
    Point = list()
    for i in range(N):
        Point.append(list(map(int, input().split())))

    
    ans = INF
    
    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    x0 = Point[i][0]
                    y0 = Point[j][1]
                    x1 = Point[k][0]
                    y1 = Point[l][1]
                    
                    if x0 >= x1 or y0 >= y1:
                        continue
                    count = 0
                    for m in range(N):
                        x, y = Point[m][0], Point[m][1]
                        if x0 <= x <= x1 and y0 <= y <= y1:
                            count += 1
                        if count >= K:
                            area = (x1 - x0) * (y1 - y0)
                            if area < ans:
                                ans = area
                            break

    print(ans)

Solution (Python):
n,k=map(int,input().split())
P,X,Y=[],[],[]
for _ in range(n):
    x,y=map(int,input().split())
    P.append((x,y))
    X.append(x)
    Y.append(y)
ans=10**19
X.sort()
Y.sort()
for d in range(n-1):
    for u in range(d,n):
        for l in range(n-1):
            for r in range(l,n):
                D,U,L,R=X[d],X[u],Y[l],Y[r]
                cnt=0
                for i in P:
                    if D<=i[0]<=U and L<=i[1]<=R:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(U-D)*(R-L))
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
P = []
for _ in range(N):
  P.append(list(map(int, input().split())))
X = sorted(set([p[0] for p in P]))
Y = sorted(set([p[1] for p in P]))

res = (X[-1] - X[0]) * (Y[-1] - Y[0])
cs = [[0] * (len(Y)) for _ in range(len(X))]

for i in range(len(X)):
  for j in range(len(Y)):
    for p in P:
      if X[0] <= p[0] <= X[i] and Y[0] <= p[1] <= Y[j]:
        cs[i][j] += 1
for l in range(len(X) - 1):
  for r in range(l + 1, len(X)):
    for d in range(len(Y) - 1):
      for u in range(d + 1, len(Y)):
        a = cs[r][u]
        if l > 0:
          a -= cs[l - 1][u]
        if d > 0:
          a -= cs[r][d - 1]
        if l > 0 and d > 0:
          a += cs[l - 1][d - 1]
        if a >= M:
          
          res = min(res, abs(X[r] - X[l]) * abs(Y[u] - Y[d]))
print(res)

Solution (Python):
n,k=map(int,input().split())
x=[0]*n;y=[0]*n
for i in range(n):x[i],y[i]=map(int,input().split())

ans=1e20
for i in range(n):
    for j in range(i+1, n):
        for a in range(n):
            for b in range(a+1, n):
                cnt=0
                x1=min(x[i],x[j])
                x2=max(x[i],x[j])
                y1=min(y[a],y[b])
                y2=max(y[a],y[b])
                for c in range(n):
                    if x1<=x[c]<=x2 and y1<=y[c]<=y2: cnt+=1
                if cnt>=k:
                    ans=min(ans,(x2-x1)*(y2-y1))
print(ans)

Solution (Python):
import sys
I = lambda:[int(x) for x in sys.stdin.readline().split()]
N,K = I()
Z = [I() for _ in range(N)]
Z.sort()

INF = 10**20
ans = INF

for i in range(N):
    for j in range(i+K-1,N):
        l = sorted(t[1] for t in Z[i:j+1])
        ans_tmp = [(Z[j][0]-Z[i][0])*(v-u) for u,v in zip(l,l[K-1:])]
        ans = min(ans,*ans_tmp)
print(ans)

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

N,K = LI()
XY = [LI() for _ in range(N)]

X = []
Y = []
for x,y in XY:
    if not(x in X):
        X.append(x)
    if not(y in Y):
        Y.append(y)
        
X.sort()
Y.sort()
dic_XoYo = {}
dic_XcYo = {}
dic_XoYc = {}
dic_XcYc = {}
for x1 in X:
  for y1 in Y:
    key = x1*(10**10)+y1
    cnt_XoYo = 0
    cnt_XcYo = 0
    cnt_XoYc = 0
    cnt_XcYc = 0
    for x2,y2 in XY:
      if x2<=x1 and y2<=y1:
        cnt_XcYc += 1
      if x2<x1 and y2<=y1:
        cnt_XoYc += 1
      if x2<=x1 and y2<y1:
        cnt_XcYo += 1
      if x2<x1 and y2<y1:
        cnt_XoYo += 1
    dic_XcYc[key] = cnt_XcYc
    dic_XoYc[key] = cnt_XoYc
    dic_XcYo[key] = cnt_XcYo
    dic_XoYo[key] = cnt_XoYo

ans = []
for xl in range(len(X)-1):
  for xr in range(xl,len(X)):
    for yd in range(len(Y)-1):
      for yu in range(yd,len(Y)):
        cnt = dic_XcYc[X[xr]*(10**10)+Y[yu]]
        cnt -= dic_XcYo[X[xr]*(10**10)+Y[yd]]
        cnt -= dic_XoYc[X[xl]*(10**10)+Y[yu]]
        cnt += dic_XoYo[X[xl]*(10**10)+Y[yd]]
        if cnt>=K:
          ans.append((X[xr]-X[xl])*(Y[yu]-Y[yd]))
print(min(ans))

Solution (Python):
N,K = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(N)]
a = sorted(ary)
ans = float("Inf")
for i in range(N-K+1):
    for j in range(i,N-K+1):
        lx = a[i][0]; rx = a[K+j-1][0]
        b = a[i:K+j]
        c = sorted(b,key=lambda x:(x[1]))
        for k in range(len(c)-K+1):
            by = c[k][1]; uy = c[k+K-1][1]
            ans = min(ans,(rx - lx) * (uy - by))
print(ans)

Solution (Python):
N, K = map(int, input().split())
x_list = [0]*N
y_list = [0]*N
for i in range(N):
    x_list[i], y_list[i] = map(int, input().split())

x_sort_list = sorted(x_list)
y_sort_list = sorted(y_list)
ans = float("inf")

for i in range(len(x_sort_list)):
    for j in range(len(y_sort_list)):
        for k in range(i+1, len(x_sort_list)):
            for l in range(j+1, len(y_sort_list)):
                num = 0
                for m in range(N):
                    if x_sort_list[i] <= x_list[m] <= x_sort_list[k] and y_sort_list[j] <= y_list[m] <= y_sort_list[l]:
                        num += 1
                if num >= K:
                    ans = min((x_sort_list[k] - x_sort_list[i]) * (y_sort_list[l] - y_sort_list[j]), ans)

print(ans)

Solution (Python):
N, K = map(int, input().split())
x_list = [0]*N
y_list = [0]*N
for i in range(N):
    x_list[i], y_list[i] = map(int, input().split())

x_element = sorted(x_list)
y_element = sorted(y_list)
ans = float("inf")

for i in range(len(x_element)):
    for j in range(len(y_element)):
        for k in range(i+1, len(x_element)):
            for l in range(j+1, len(y_element)):
                num = 0
                for m in range(N):
                    if x_element[i] <= x_list[m] <= x_element[k] and y_element[j] <= y_list[m] <= y_element[l]:
                        num += 1
                if num >= K:
                    ans = min((x_element[k] - x_element[i]) * (y_element[l] - y_element[j]), ans)

print(ans)

Solution (Python):
from itertools import combinations

n,k = map(int,input().split())
Px = sorted([list(map(int,input().split())) for i in range(n)])
Py = sorted(Px,key=lambda p:p[1])

area = float('inf')

for x1 in range(n-1):
    for x2 in range(x1+1,n):
        for y1 in range(n-1):

            point = 0
            for y in range(y1,n):
                if Px[x1][0]<=Py[y][0]<=Px[x2][0]:
                    point += 1
                    if point == k:
                        area = min(area,(Px[x2][0]-Px[x1][0])*(Py[y][1]-Py[y1][1]))
                        break

print(area)

Solution (Python):
n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary.sort()

ans = float("Inf")
for i in range(n-k+1):
    for j in range(k,n-i+1):
        xmin = ary[i][0]
        xmax = ary[i+j-1][0]
        ary_y = sorted(ary[i:i+j], key=lambda x: (x[1]))
        for l in range(len(ary_y)-k+1):
            ymin = ary_y[l][1]
            ymax = ary_y[l+k-1][1]
            ans = min(ans,(xmax - xmin) * (ymax - ymin))
print(ans)

Solution (Python):
N,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
s = 10**19
B = sorted(A,key=lambda x:x[0])
for i in range(N-K+1):
    for j in range(K,N-i+1):
        xmin = B[i][0]
        xmax = B[i+j-1][0]
        By = sorted(B[i:i+j],key=lambda x:x[1])
        for k in range(len(By)-K+1):
            ymin = By[k][1]
            ymax = By[k+K-1][1]
            s = min(s,(xmax-xmin)*(ymax-ymin))
print(s)

Solution (Python):
N, K = map(int, input().split())
x_list = []
y_list = []
xy_list = []
for _ in range(N):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)
    xy_list.append((x, y))
x_dict = {}
x_dict_rev = {}
y_dict = {}
y_dict_rev = {}
x_list.sort()
y_list.sort()
for i, xi in enumerate(x_list):
    x_dict[xi] = i
    x_dict_rev[i] = xi
for i, yi in enumerate(y_list):
    y_dict[yi] = i
    y_dict_rev[i] = yi
xy_c = [[0 for _ in range(N)] for _ in range(N)]
for x, y in xy_list:
    xy_c[x_dict[x]][y_dict[y]] = 1

cs = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        cs[i+1][j+1] = cs[i+1][j] + cs[i][j+1] - cs[i][j] + xy_c[i][j]

ans = float('inf')
for x_min in range(1, N+1):
    for x_max in range(1, N+1):
        for y_min in range(1, N+1):
            for y_max in range(1, N+1):
                if cs[x_max][y_max] - cs[x_min-1][y_max] - cs[x_max][y_min-1] + cs[x_min-1][y_min-1] >= K:
                    ans = min(ans, (x_dict_rev[x_max-1] - x_dict_rev[x_min-1]) * (y_dict_rev[y_max-1] - y_dict_rev[y_min-1]))


print(ans)

Solution (Python):
import sys
from bisect import bisect_left
input = sys.stdin.readline

n, k = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]

x = [p[i][0] for i in range(n)]
x.sort()
y = [p[i][1] for i in range(n)]
y.sort()

coord = [[0] * n for i in range(n)]
for i in range(n):
    x_idx = bisect_left(x, p[i][0])
    y_idx = bisect_left(y, p[i][1])
    coord[x_idx][y_idx] += 1

coord_cs = [[0] * (n+1) for i in range(n+1)]
for i in range(n):
    for j in range(n):
        coord_cs[i+1][j+1] = coord[i][j]
for i in range(n):
    for j in range(n+1):
        coord_cs[i+1][j] += coord_cs[i][j]
for i in range(n+1):
    for j in range(n):
        coord_cs[i][j+1] += coord_cs[i][j]




ans = (x[-1] - x[0]) * (y[-1] - y[0])
for xi in range(n):
    for xj in range(xi+1, n+1):
        for yi in range(n):
            for yj in range(yi+1, n+1):
                if coord_cs[xj][yj] - coord_cs[xi][yj] - coord_cs[xj][yi] + coord_cs[xi][yi] == k:
                    cand = (x[xj-1] - x[xi]) * (y[yj-1] - y[yi])
                    ans = min(ans, cand)

print(ans)

Solution (Python):
N, K = map(int, input().split())
x_list = [0]*N
y_list = [0]*N
for i in range(N):
    x_list[i], y_list[i] = map(int, input().split())

x_element = sorted(set(x_list))
y_element = sorted(set(y_list))
ans = float("inf")

for i in range(len(x_element)):
    for j in range(len(y_element)):
        for k in range(i+1, len(x_element)):
            for l in range(j+1, len(y_element)):
                num = 0
                for m in range(N):
                    if x_element[i] <= x_list[m] <= x_element[k] and y_element[j] <= y_list[m] <= y_element[l]:
                        num += 1
                if num >= K:
                    ans = min((x_element[k] - x_element[i]) * (y_element[l] - y_element[j]), ans)

print(ans)

Solution (Python):
n,h=map(int,input().split())
p,x,y=[],[],[]
z=float("inf")
for i in range(n):
  a,b=map(int,input().split())
  p.append((a,b))
  x.append(a)
  y.append(b)
x.sort()
y.sort()
for i in range(n-1):
  for j in range(i,n):
    for k in range(n-1):
      lx,rx,dy=x[i],x[j],y[k]
      c=0
      t=[]
      for a,b in p:
        if x[i]<=a<=x[j] and y[k]<=b:c+=1;t.append(b)
      if h<=c:z=min(z,(x[j]-x[i])*(sorted(t)[h-1]-y[k]))
print(z)

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):
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(N)]
    
    xs = []
    ys = []
    xy = sorted(xy, key=lambda x: x[0])
    for i in range(N):
        xs.append(xy[i][0])
        xy[i][0] = i+1
    xy = sorted(xy, key=lambda x: x[1])
    for i in range(N):
        ys.append(xy[i][1])
        xy[i][1] = i+1
    
    sum_ = np.zeros((N+1, N+1), dtype=int)
    for i in range(N):
        x, y = xy[i]
        sum_[y][x] = 1
    for i in range(1, N+1):
        sum_[i] += sum_[i-1]
    for i in range(1, N+1):
        sum_[:,i] += sum_[:,i-1]
    
    ans = int(1e20)
    for l in range(1, N+1):
        no_three = True
        for r in range(N, l, -1):
            no_two = True
            for d in range(1, N+1):
                no_one = True
                for u in range(d+1, N+1):
                    tmp = sum_[u][r] - sum_[d-1][r] - sum_[u][l-1] + sum_[d-1][l-1]
                    if tmp >= K:
                        tmp = (xs[r-1] - xs[l-1]) * (ys[u-1] - ys[d-1])
                        ans = min(ans, tmp)
                        no_one = False
                        break
                if no_one:
                    break
                else:
                    no_two = False
            if no_two:
                break
            else:
                no_three = False
        if no_three:
            break
                

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
INF = float("inf")

N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

ans = INF
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        for j in range(k - K + 1):
            dy = YY[j + K - 1] - YY[j]
            if ans > dx * dy:
                ans = dx * dy

print(ans)

Solution (Python):
N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

cand = []
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        cand += [min(dx * (YY[j + K - 1] - YY[j]) for j in range(k - K + 1))]

print(min(cand))

Solution (Python):
N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

cand = []
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        cand.append(min(dx * (YY[j + K - 1] - YY[j]) for j in range(k - K + 1)))

print(min(cand))

Solution (Python):
N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

ans = 1e20
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        ans = min(ans, min(dx * (YY[j + K - 1] - YY[j]) for j in range(k - K + 1)))

print(ans)

Solution (Python):
N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

cand = []
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        cand += [dx * (YY[j + K - 1] - YY[j]) for j in range(k - K + 1)]

print(min(cand))

Solution (Python):
INF = float("inf")

N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

ans = INF
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        for j in range(k - K + 1):
            dy = YY[j + K - 1] - YY[j]
            ans = min(ans, dx * dy)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    from itertools import product
    n,k=map(int,input().split())
    X=[0]*n
    Y=[0]*n
    XY=[0]*n
    for i in range(n):
        x,y=map(int,input().split())
        X[i]=x
        Y[i]=y
        XY[i]=(x,y)
    
    S=[[0]*n for _ in range(n)]
    X.sort(); Y.sort()
    for i,j in product(range(n),repeat=2):
        for x,y in XY:
            if x<=X[i] and y<=Y[j]: S[i][j]+=1
    
    ans=INF
    for i0,j0 in product(range(n),repeat=2):
        for i1,j1 in product(range(i0+1,n),range(j0+1,n)):
            count=S[i1][j1]
            if i0>0: count-=S[i0-1][j1]
            if j0>0: count-=S[i1][j0-1]
            if i0>0 and j0>0: count+=S[i0-1][j0-1]
            if count>=k:
                ans=min(ans,(X[i1]-X[i0])*(Y[j1]-Y[j0]))
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    X=[0]*n
    Y=[0]*n
    for i in range(n):
        X[i],Y[i]=map(int,input().split())
    ans=INF
    for a in range(n):
        for b in range(n):
            for c in range(a+1,n):
                for d in range(b+1):
                    x0,x1=sorted([X[a],X[c]])
                    y0,y1=sorted([Y[b],Y[d]])
                    count=0
                    for i in range(n):
                        if x0<=X[i]<=x1 and y0<=Y[i]<=y1:
                            count+=1
                    if count>=k:
                        ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

Solution (Python):
n,k=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
    x[i],y[i]=map(int,input().split())
ans=float('inf')
for i1 in range(n):
    for i2 in range(i1+1,n):
        for j1 in range(n):
            for j2 in range(j1+1,n):
                a,b=sorted([x[i1],x[i2]])
                c,d=sorted([y[j1],y[j2]])
                cnt=0
                for i in range(n):
                    if a<=x[i]<=b and c<=y[i]<=d:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(b-a)*(d-c))
print(ans)

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

ans = float("inf")
for i in range(N):
    x1,y1 = XY[i]
    for j in range(i+1,N):
        x2,y2 = XY[j]
        u2 = max(y1,y2)
        d2 = min(y1,y2)
        r2 = max(x1,x2)
        l2 = min(x1,x2)
        for k in range(j+1,N):
            x3,y3 = XY[k]
            u3 = max(u2,y3)
            d3 = min(d2,y3)
            r3 = max(r2,x3)
            l3 = min(l2,x3)
            for kk in range(k+1,N):
                x4,y4 = XY[kk]
                u4 = max(u3,y4)
                d4 = min(d3,y4)
                r4 = max(r3,x4)
                l4 = min(l3,x4)
                num = 0
                for m in range(N):
                    x,y = XY[m]
                    if l4<=x<=r4 and d4<=y<=u4:
                        num += 1
                if num >= K:
                    tmp = (u4-d4)*(r4-l4)
                    if tmp < ans:
                        ans = tmp
            num = 0
            for m in range(N):
                x,y = XY[m]
                if l3<=x<=r3 and d3<=y<=u3:
                    num += 1
            if num >= K:
                tmp = (u3-d3)*(r3-l3)
                if tmp < ans:
                    ans = tmp
        num = 0
        for m in range(N):
            x,y = XY[m]
            if l2<=x<=r2 and d2<=y<=u2:
                num += 1
        if num >= K:
            tmp = (u2-d2)*(r2-l2)
            if tmp < ans:
                ans = tmp
print(ans)

Solution (Python):
N, K = map(int, input().split())
p_list = [[0] * 2 for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    p_list[i] = [x, y]

p_list.sort()
ans = float('inf')
for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        x = abs(p_list[j][0] - p_list[i][0])
        y_list = []
        for k in range(i, j + 1):
            y_list.append((p_list[k][1]))
        y_list.sort()
        for k in range(len(y_list) - K + 1):
            ans = min(ans, x * abs(y_list[k + K - 1] - y_list[k]))

print(ans)

Solution (Python):
N, K = map(int, input().split())
xys = []
for i in range(N):
  x, y = map(int, input().split())
  xys.append((x, y))
xs = sorted(map(lambda xy: xy[0], xys))
ys = sorted(map(lambda xy: xy[1], xys))
rs = []
for i in range(N):
  for j in range(i+1, N):
    x1 = xs[i]
    x2 = xs[j]
    for k in range(N):
      for l in range(k+1, N):
        y1 = ys[k]
        y2 = ys[l]
        n = len([(x, y) for x, y in xys if x1 <= x <= x2 and y1 <= y <= y2])
        
        if n >= K:
          r = (x2-x1)*(y2-y1)
          rs.append(r)
r = min(rs)
print(r)

Solution (Python):
n,k=map(int,input().split())
P=[list(map(int,input().split())) for _ in range(n)]
X=sorted(list(map(lambda x:x[0],P)))
Y=sorted(list(map(lambda x:x[1],P)))
s=(X[0]-X[-1])*(Y[0]-Y[-1])
ans=0
for r in range(n-1,0,-1):
  for l in range(r):
    for u in range(n-1,0,-1):
      for b in range(u):
        c=0
        for p in P:
          if X[l]<=p[0]<=X[r] and Y[b]<=p[1]<=Y[u]:
            c+=1
        if c>=k:
          s=min(s,(X[r]-X[l])*(Y[u]-Y[b]))
        else:break
    if u==n-1 and b==0 and c<k:
      break
print(s)

Solution (Python):
import itertools
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    X = []
    Y = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    
    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):
                    cnt = 0
                    for p in range(N):
                        if min(X[i], X[j])<=X[p] and X[p]<=max(X[i], X[j]):
                            if min(Y[k], Y[l])<=Y[p] and Y[p]<=max(Y[k], Y[l]):
                                cnt += 1
                    if cnt>=K:
                        s = abs(X[i]-X[j]) * abs(Y[k]-Y[l])
                        if s!=0:
                            ans = min(ans, s)
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
XY = [[0, 0, 0] for _ in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y, i]
X = sorted(XY)
Y = sorted(XY, key=lambda x: x[1])
rect = (X[-1][0] - X[0][0]) * (Y[-1][1] - Y[0][1])
for l in range(N - K + 1):
  for r in range(l + K - 1, N):
    for d in range(N - K + 1):
      for u in range(d + K - 1, N):
        if len([x for x in XY if X[l][0] <= x[0] <= X[r][0] and Y[d][1] <= x[1] <= Y[u][1]]) >= K:
          rect = min((X[r][0] - X[l][0]) * (Y[u][1] - Y[d][1]), rect)
print(rect)

Solution (Python):
def main():
    N, K = map(int, input().split())
    x = [0] * N
    y = [0] * N

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

    ans = float('inf')
    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    if x[i] < x[j] and y[k] < y[l]:
                        cnt = 0
                        lx = x[i]
                        rx = x[j]
                        by = y[k]
                        uy = y[l]

                        for n in range(N):
                            if lx <= x[n] and x[n] <= rx and by <= y[n] and y[n] <= uy:
                                cnt += 1

                        if cnt >= K:
                            ans = min(ans, (rx - lx) * (uy - by))

    print(ans)

main()

Solution (Python):

N,K = map(int,input().split())

xy = []
xlis = []
ylis = []

for i in range(N):

    x,y = map(int,input().split())

    xy.append([x,y])

    if x not in xlis:
        xlis.append(x)
    if y not in ylis:
        ylis.append(y)

ans = float("inf")
xlis.sort()
ylis.sort()

for rp in range(len(xlis)):

    right = xlis[rp]

    for lp in range(rp+1):

        left = xlis[lp]

        for upp in range(len(ylis)):

            up = ylis[upp]

            for dp in range(upp+1):

                down = ylis[dp]

                able = 0
                nable = 0
                for i in range(N):

                    nx = xy[i][0]
                    ny = xy[i][1]
                    if left <= nx and nx <= right and down <= ny and ny <= up:
                        able += 1
                    else:
                        nable += 1

                    if able >= K or nable > N-K:
                        break

                if able >= K:
                    now = max(1,right-left) * max(1,up-down)
                    ans = min(ans,now)

print (ans)

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

P = []
X = []
Y = []

PAppend = P.append
XAppend = X.append
YAppend = Y.append
for i in range(N):
  PAppend([int(x) for x in input().split()])
  XAppend(P[i][0])
  YAppend(P[i][1])

X.sort()
Y.sort()

S = [[0] * N for _ in range(N)]
for i in range(N):
  for j in range(N):
    for k in P:
      if k[0] <= X[i] and k[1] <= Y[j]:
        S[i][j] += 1

ans = float('inf')
for i in range(N - 1):
  for j in range(N - 1):
    for k in range(i + 1, N):
      for l in range(j + 1, N):
        PCount = S[k][l]
        if i > 0:
          PCount -= S[i - 1][l]
        if j > 0:
          PCount -= S[k][j - 1]
        if i > 0 and j > 0:
          PCount += S [i - 1][j - 1]
        if PCount >= K:
          ans = min(ans, (X[k] - X[i]) * (Y[l] - Y[j]))

print(ans)

Solution (Python):

import sys, itertools


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    mn = 1e25
    for X in itertools.combinations(x, 2):
        for Y in itertools.combinations(y, 2):
            if len([xx for (xx, yy) in zip(x, y) if (X[0]-xx)*(X[1]-xx)<=0 and (Y[0]-yy)*(Y[1]-yy)<=0]) >= K:
                mn = min(mn, abs(X[0] - X[1]) * abs(Y[0] - Y[1]))
    print(mn)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)

if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
P,X,Y=[],[],[]
for _ in range(n):
    x,y=map(int,input().split())
    P.append((x,y))
    X.append(x)
    Y.append(y)
ans=10**19
X.sort()
Y.sort()
for d in range(n-1):
    for u in range(d,n):
        for l in range(n-1):
            for r in range(n):
                D,U,L,R=X[d],X[u],Y[l],Y[r]
                cnt=0
                for i in P:
                    if D<=i[0]<=U and L<=i[1]<=R:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(U-D)*(R-L))
print(ans)

Solution (Python):
import itertools
import math


LIM = 50
N,K = list(map(int,input().split(" ")))

Xs = []
Ys = []

dots = []
for _ in range(N):
    x,y = (map(int,input().split(" ")))
    Xs.append(x)
    Ys.append(y)
    dots.append((x,y))

Xs.sort()
Ys.sort()

ans = -1
for x1 in range(N):
    for x2 in range(x1 + 1,N):
        for y1 in range(N):
            for y2 in range(y1 + 1,N):
                cot = 0
                underX = Xs[x1]
                upperX = Xs[x2]
                underY = Ys[y1]
                upperY = Ys[y2]

                for k in range(N):
                    if   underX<= dots[k][0] <= upperX and underY <= dots[k][1] <= upperY:
                        cot += 1
                if cot >= K:
                    S = (upperX - underX) * (upperY - underY)
                    if ans == -1:
                        ans = S
                    ans = min( ans ,S)
print(ans)

Solution (Python):
def main():
 
    N, K = map(int, input().split())
    p = []
    for _ in range(N):
        x, y = map(int, input().split())
        p.append([x, y])
    p.sort(key = lambda x: x[0])
 
    min_area = float('inf')
    for i in range(N-1):
        for j in range(i+1, N):
            if j-i+1 >= K:
                x1 = p[i][0]
                x2 = p[j][0]
                ys = []
                for k in range(i, j+1):
                    ys.append(p[k][1])
                ys.sort()
                for k in range(len(ys)):
                    for l in range(k+K-1, len(ys)):
                        y1 = ys[k]
                        y2 = ys[l]
                        area = (x2-x1)*(y2-y1)
                        if area > 0:
                            min_area = min(min_area, area)
    return min_area
 
if __name__ == '__main__':
    print(main())