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):
N,K=map(int,input().split())
point=[tuple(map(int,input().split())) for i in range(N)]
point.sort(key=lambda x:x[0])
ans=float('inf')
for i in range(1+N-K):
    for j in range(i+K,N+1):
        x=point[j-1][0]-point[i][0]
        now=point[i:j]
        now.sort(key=lambda x:x[1])
        for k in range(j-i-K+1):
            ans=min(x*(now[k+K-1][1]-now[k][1]),ans)
print(ans)

Solution (Python):
from functools import reduce
import math

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N, K = (int(_) for _ in input().split())
    p = []
    for i in range(N):
        x,y = (int(_) for _ in input().split())
        p.append((x,y))
        
    ans = INF
    for i in range(N):
        for j in range(i+1,N):
            for h in range(N):
                for g in range(h+1,N):
                    x_start = min(p[i][0],p[j][0])
                    y_start = min(p[h][1],p[g][1])
                    x_end = max(p[i][0],p[j][0])
                    y_end = max(p[h][1],p[g][1])
                    area = (x_end - x_start) * (y_end - y_start)
                    cnt = 0
                    for k in range(N):
                        if p[k][0] >= x_start and p[k][1] >= y_start and p[k][0] <= x_end and p[k][1] <= y_end:
                            cnt += 1
                            if cnt == K:
                                ans = min(ans,area)
                                break
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
import copy

n,k = getList()
buff = []
for i in range(n):
    buff.append(getList())

def calc(width, cutbuf, k):
    nn= len(cutbuf)
    cutbuf.sort(key=lambda x: x[1])
    ret = 10**19
    for ii in range(nn-k+1):
        tmptmp = abs(cutbuf[ii][1] - cutbuf[ii+k-1][1])
        
        if ret > tmptmp:
            
            ret = tmptmp
    
    return ret*width
buff.sort()
ans = 10**19
for i in range(n):
    for j in range(i+1, n):
        width = abs(buff[i][0] - buff[j][0])
        tmp = calc(width, buff[i:j+1], k)

        if ans > tmp:
            ans = tmp

print(ans)

Solution (Python):
N,K=map(int, input().split())
p=[[int(x) for x in input().split()] for _ in range(N)]

xs=[x for x,_ in p]
ys=[y for _,y in p]
q=[(x,y) for x in xs for y in ys]

up=[set() for _ in range(len(q))]
dn=[set() for _ in range(len(q))]

for i in range(len(q)):
	xi,yi=q[i]
	for j in range(len(p)):
		xj,yj=p[j]
		if xj >= xi and yj >= yi:
			up[i].add(j)
		if xj <= xi and yj <= yi:
			dn[i].add(j)

ans=10**999

for i in range(len(q)):
	for j in range(len(q)):
		if len(up[i] & dn[j]) >= K:
			xi,yi=q[i]
			xj,yj=q[j]
			ans=min(ans, abs(xj-xi)*abs(yj-yi))

print(ans)

Solution (Python):
N,K = map(int,input().split())
xy = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x:(x[0],x[1]))

ans = 10**20

for i in range(K,N+1):
    for j in range(0,N-i+1):
        xy2 = sorted(xy[j:j+i],key = lambda x:(x[1]))
        for k in range(0,i-K+1):
            xy3 = xy2[k:k+K]
            Y_wid = xy3[-1][1] - xy3[0][1]
            x3 = [tmp for tmp,_ in xy3]
            X_wid = max(x3) - min(x3)
            ans = min(ans,X_wid*Y_wid)
print(ans)

Solution (Python):
from itertools import combinations

n, k = map(int, input().split())
xlist, ylist, xy = [], [], []
for _ in range(n):
  x, y = map(int, input().split())
  xlist.append(x)
  ylist.append(y)
  xy.append((x, y))

xlist.sort()
ylist.sort()
ans = (xlist[-1] - xlist[0]) * (ylist[-1] - ylist[0])
for x1, x2 in combinations(xlist, r=2):
  for y1, y2 in combinations(ylist, r=2):
    tmpk = 0
    for i in range(n):
      if x1 <= xy[i][0] <= x2 and y1 <= xy[i][1] <= y2:
        tmpk += 1

      if tmpk >= k:
        tmp_ans = (x2 - x1) * (y2 - y1)
        if ans > tmp_ans:
          ans = tmp_ans

print(ans)

Solution (Python):
n, K = map(int,input().split())
xarr = []
yarr = []
src = []
for _ in range(n):
    x, y = map(int,input().split())
    src.append([x,y])
    xarr.append(x)
    yarr.append(y)

xarr.sort()
yarr.sort()
ans = float('inf')
for i in range(n):
    for j in range(i + 1, n):
        for k in range(n):
            for l in range(k + 1, n):
                cnt = 0
                for m in range(n):
                    if src[m][0] >= xarr[i] and src[m][0] <= xarr[j] and src[m][1] >= yarr[k] and src[m][1] <= yarr[l]:
                        cnt += 1
                if cnt >= K:
                    ans = min((xarr[i]-xarr[j])*(yarr[k]-yarr[l]), ans)

print(ans)

Solution (Python):
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n, k1 = f()

    pts = []
    sety = set()
    setx = set()
    for i in range(n):
        x, y = f()
        pts.append((x,y))
        setx.add(x)
        sety.add(y)
    
    minarea = int(1e19)

    xlist = list(setx)
    ylist = list(sety)
    xl = len(xlist)
    yl = len(ylist)

    ylist = sorted(ylist)
    xlist = sorted(xlist)

    xindx = dict(zip(xlist, range(xl)))

    for i in range(yl):
        for j in range(i+1, yl):
            cnt = [0] * xl
            for l in range(n):
                if pts[l][1] >= ylist[i] and pts[l][1]<=ylist[j]:
                    cnt[xindx[pts[l][0]]] += 1


            head = 0
            end = 0
            total = 0
            while end<xl:
                total += cnt[end]

                while total >= k1:
                    minarea = min(minarea, (ylist[j] - ylist[i]) * (xlist[end] - xlist[head]))
                    total -= cnt[head]
                    head += 1

                end += 1
    
    print(minarea)
                    








solve()

Solution (Python):
N, K = map(int, input().split())
p = [list(map(int, input().split())) for i in range(N)]
t, b, l, r = 0, 0, 0, 0
area = []


for i in range(N):
  t = p[i][1]
  p1 = [a for a in p if a[1] <= t]

  for j in range(len(p1)):
    b = p1[j][1]
    p2 = [a for a in p1 if a[1] >= b]

    for k in range(len(p2)):
      r = p2[k][0]
      p3 = [a for a in p2 if a[0] <= r]

      for m in range(len(p3)):
        l = p3[m][0]
        p4 = [a for a in p3 if a[0] >= l]

        if len(p4) >= K:
          tmp = (l-r)*(t-b)
          area.append(abs(tmp))
print(min(area))

Solution (Python):
def main():
	N, K = map(int,input().split())
	points = [0]*N
	max_x, max_y, min_x, min_y = -10**9, -10**9, 10**9, 10**9
	for i in range(N):
		points[i] = list(map(int, input().split()))
		max_x = max(max_x, points[i][0])
		min_x = min(min_x, points[i][0])
		max_y = max(max_y, points[i][1])
		min_y = min(min_y, points[i][1])

	points.sort(key=lambda x:x[0])
	ans = (max_x-min_x)*(max_y-min_y)
	for r in range(K, N+1):
		for l in range(N-r+1):
			w = points[r+l-1][0] - points[l][0]
			this_points = sorted(list(points[l:l+r]), key=lambda x:x[1])
			for b in range(r-K+1):
				h = this_points[b+K-1][1] - this_points[b][1]
				ans = min(ans, w*h)
	print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
 
inf = float('inf')
 
def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    V = [(x[i], y[i]) for i in range(N)]
    V.sort()
    X = [v[0] for v in V]
    Y = [v[1] for v in V]
    res = inf
    for k in range(K, N+1):
        for i in range(N-k+1):
            delta_x = X[i+k-1] - X[i]
            yy = sorted(Y[i:i+k])
            for j in range(k-K+1):
                delta_y = yy[j+K-1] - yy[j]
                s = delta_x * delta_y
                if s < res:
                    res = s
 
    print(res)
    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):
import itertools

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

X = []
Y = []

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



min_area = 5*10**18

for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if x1 > x2:
      x1,x2 = x2,x1
    if y1 > y2:
      y1,y2 = y2,y1

    area = (x2-x1) * (y2-y1)
    if area > min_area:
      continue
      
    cnt = 0
    for x,y in zip(X,Y):
      if x1 <= x <= x2 and y1 <= y <= y2:
        cnt += 1
    if cnt < K:
      continue
      
    min_area = area
    
print(min_area)

Solution (Python):
def solve():
    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())
    inf=1<<62
    ans=inf
    for x1 in X:
        for x2 in X:
            if x1 <= x2:
                for y1 in Y:
                    for y2 in Y:
                        if y1 <= y2:
                            cnt = 0
                            for i in range(N):
                                if x1 <= X[i] <= x2 and y1 <= Y[i] <= y2:
                                    cnt += 1
                            if cnt >= K:
                                ans = min(ans, (x2-x1)*(y2-y1))
    return ans

print(solve())

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

ans = 10 ** 19
for a in range(N):
    for b in range(a+1, N):
        for c in range(N):
            for d in range(c+1, N):
                x0 = data[a][0]
                x1 = data[b][0]
                y0 = data[c][1]
                y1 = data[d][1]

                if x0 > x1:
                    x0, x1 = x1, x0
                if y0 > y1:
                    y0, y1 = y1, y0

                count = 0
                for i, j in data:
                    if x0 <= i <= x1 and y0 <= j <= y1:
                        count += 1
                if count >= K:
                    ans = min(ans, (x1 - x0)*(y1 - y0))

print(ans)

Solution (Python):
inf = float('inf')

N,K = map(int,input().split())
ans = inf
X = []
Y = []
XY = []
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
    XY.append((x,y))

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

for i, left in enumerate(X):
    for right in X[i+1:]:
        for j, bottom in enumerate(Y):
            for top in Y[j+1:]:
                cnt = 0
                for x, y in XY:
                    if left <= x <= right and bottom <= y <= top:
                        cnt += 1
                S = (right-left)*(top-bottom)
                if cnt >= K and S < ans:
                    ans = S

print(ans)

Solution (Python):
inf = float('inf')

N,K = map(int,input().split())
ans = inf
X = []
Y = []
XY = []
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
    XY.append((x,y))

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

for i, left in enumerate(X):
    for right in X[i+1:]:
        for j, bottom in enumerate(Y):
            for top in Y[j+1:]:
                cnt = 0
                for x, y in XY:
                    if left <= x <= right and bottom <= y <= top:
                        cnt += 1
                if cnt < K: continue
                S = (right-left)*(top-bottom)
                if S < ans:
                    ans = S

print(ans)

Solution (Python):
inf = float('inf')

N,K = map(int,input().split())
ans = inf
X = []
Y = []
XY = []
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
    XY.append((x,y))

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

for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                cnt = 0
                for x, y in XY:
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        cnt += 1
                if cnt < K: continue
                S = (Y[l]-Y[k])*(X[j]-X[i])
                if S < ans:
                    ans = S

print(ans)

Solution (Python):
def count_inner(P, x1, y1, x2, y2):
    cnt = 0
    for p in P:
        if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
            cnt += 1
    return cnt


def main():
    N, K = map(int, input().split())
    P = [None] * N
    xs = [0] * N
    ys = [0] * N
    for i in range(N):
        x, y = map(int, input().split())
        P[i] = (x, y)
        xs[i] = x
        ys[i] = y
    xs.sort()
    ys.sort()
    ans = float("inf")
    for i in range(N):
        for j in range(i+1, N):
            for k in range(N):
                for l in range(k+1, N):
                    if count_inner(P, xs[i], ys[k], xs[j], ys[l]) >= K:
                        ans = min(ans, (xs[j] - xs[i]) * (ys[l] - ys[k]))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field

def compress(xy_row: list, x_compressor, y_compressor):
    xy_comped = []
    for xi, yi in xy_row:
        xy_comped.append((x_compressor[xi], y_compressor[yi]))
        
    return xy_comped

def decompress(comped: list, x_decomp, y_decomp):
    xy_decomped = []
    for xi, yi in comped:
        xy_decomped.append((x_decomp[xi], y_decomp[yi]))
        
    return xy_decomped

n,k = li()
xy_row = [tuple(li()) for _ in range(n)]

x_row = [x for x, _ in sorted(xy_row, key=lambda x:x[0])]
y_row = [y for _, y in sorted(xy_row, key=lambda y:y[1])]

x_compressor = {xi: i+1 for i, xi in enumerate(x_row)}
y_compressor = {yi: i+1 for i, yi in enumerate(y_row)}
x_decomp = {i+1: xi for i, xi in enumerate(x_row)}
y_decomp = {i+1: yi for i, yi in enumerate(y_row)}

xy_comped = compress(xy_row, x_compressor, y_compressor)


grid = [[0]*(len(xy_comped)+1) for _ in range(len(xy_comped)+1)]
for xi, yi in xy_comped:
    grid[xi][yi] += 1
    
grid = cum_2d(grid)

ans = float('inf')

for xleft in range(1,n+1):
    for xright in range(xleft, n+1):
        for ylow in range(1,n+1):
            for yhigh in range(ylow, n+1):
                if grid[xright][yhigh] - grid[xright][ylow-1] - grid[xleft-1][yhigh] + grid[xleft-1][ylow-1] < k:
                    continue
                
                xnw = x_decomp[xleft]
                xne = x_decomp[xright]
                
                yne = y_decomp[yhigh]
                yse = y_decomp[ylow]

                ans = min(ans, (xne-xnw)*(yne-yse))
                
print(ans)

Solution (Python):
from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
cum = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + ([xsort[i][0], ysort[j][1]] in xy)

def count_points_in_rec(x0, x1, y0, y1):
    point = cum[x1+1][y1+1] - cum[x0][y1+1] - cum[x1+1][y0] + cum[x0][y0]
    return point

ans = 5 * 10**18
comb = []
for a, b in combinations(l, 2):
    if b - a >= k-1:
        comb.append([a, b])
for a, b in comb:
    for c, d in comb:
        if count_points_in_rec(a, b, c, d) == k:
            ans = min(ans, (xsort[b][0]-xsort[a][0]) * (ysort[d][1]-ysort[c][1]))
print(ans)

Solution (Python):

N,K = map(int,input().split())
locations = [tuple(map(int,input().split())) for _ in range(N)]

locations.sort()





minimalArea = (10**18)*5
for i in range(N-K+1):
    for j in range(i+K-1,N):
        deltaX = locations[j][0] - locations[i][0]
        sliced = locations[i:j+1]
        sliced.sort(key= lambda p: p[1])
        
        length = j-i+1
        if length < K:
            continue
        for k in range(length-K+1):
            deltaY = sliced[k + K - 1][1] - sliced[k][1]
            area = deltaX * deltaY
            
            
            minimalArea = min(area,minimalArea)
print(minimalArea)

Solution (Python):
n, kk = map(int, input().split())
p = [list(map(int, input().split())) for i in range(n)]
x_set = set(i[1] for i in p)
y_set = set(i[0] for i in p)
d_x = {}
d_y = {}
for i, x in enumerate(sorted(list(x_set))):
    d_x[x] = i
for i, y in enumerate(sorted(list(y_set))):
    d_y[y] = i
g_x = {}
g_y = {}
w = len(d_x)
h = len(d_y)
board = [[0]*(w+1) for i in range(h+1)]
tmp = [[0]*h for i in range(w)]
for y, x in p:
    ys = d_y[y]
    xs = d_x[x]
    g_x[xs] = x
    g_y[ys] = y
    tmp[ys][xs] += 1
for i in range(h):
    for j in range(w):
        board[i+1][j+1] = board[i+1][j] + board[i][j+1] - board[i][j] + tmp[i][j]


ans = float("inf")
for i in range(h-1):
    for j in range(i+1, h):
        for k in range(w-1):
            for l in range(k+1, w):
                s = board[j+1][l+1] - board[i][l+1] - board[j+1][k] + board[i][k]
                if s >= kk:
                    
                    area = (g_y[j] - g_y[i]) * (g_x[l] - g_x[k])
                    ans = min(ans, area)
print(ans)

Solution (Python):
n, k = map(int, input().split())
p = [list(map(int, input().split())) for i in range(n)]
ans = float("inf")

p.sort()
for i in range(n-k+1):
    for j in range(i+k-1, n):
        x = p[j][0] - p[i][0]
        yl = sorted(p[i:j+1],key=lambda x:x[1])
        for l in range(len(yl)-k+1):
            y = yl[l+k-1][1] - yl[l][1]
            ans = min(ans, y*x)
print(ans)

Solution (Python):
N,K=map(int,input().split())
ans=float('inf')
point=[tuple(map(int,input().split())) for i in range(N)]
point.sort(key=lambda x:x[0])
for i in range(N-K+1):
    for j in range(i+K,N+1):
        check=point[i:j]
        x=check[-1][0]-check[0][0]
        check.sort(key=lambda x:x[1])
        for k in range(j-i-K+1):
            y=check[k+K-1][1]-check[k][1]
            ans=min(ans,x*y)
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=[list(map(int,input().split()))for i in range(n)]
a.sort()
b=float("inf")
for i in range(n-k+1):
    for j in range(i+k-1,n):
        p=a[j][0]-a[i][0]
        c=sorted([d[1] for d in a[i:j+1]])
        for s in range(j-i-k+2):
            q=c[s+k-1]-c[s]
            b=min(b,p*q)
print(b)

Solution (Python):
def axis_parallel_rectangle(N: int, K: int, xy: list)->int:
    
    sorted_x = sorted(v[0] for v in xy)
    sorted_y = sorted(v[1] for v in xy)

    XY = [(sorted_x.index(v[0]), sorted_y.index(v[1])) for v in xy]
    
    S = [[0] * (N+1) for _ in range(N+1)]
    for x, y in XY:
        S[x+1][y+1] = 1

    for x in range(N+1):
        for y in range(N):
            S[x][y+1] += S[x][y]

    for y in range(N+1):
        for x in range(N):
            S[x+1][y] += S[x][y]

    
    min_area = 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):
                    count = S[x2+1][y2+1]-S[x2+1][y1]-S[x1][y2+1]+S[x1][y1]
                    if count < K:
                        continue
                    xmin, xmax = sorted_x[x1], sorted_x[x2]
                    ymin, ymax = sorted_y[y1], sorted_y[y2]
                    min_area = min(min_area, (xmax-xmin)*(ymax-ymin))
    
    return min_area


if __name__ == "__main__":
    N = 0
    N, K = map(int, input().split())
    xy = [tuple(map(int, input().split())) for _ in range(N)]
    ans = axis_parallel_rectangle(N, K, xy)
    print(ans)

Solution (Python):
n, k = map(int, input().split())
p = [tuple(map(int, input().split())) for _ in range(n)]
xlist = []
ylist = []
for x, y in p:
    xlist.append(x)
    ylist.append(y)
xlist.sort()
ylist.sort()
cum = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + ((xlist[i], ylist[j]) in p)
minarea = 10 ** 20
for l in range(n-1):
    for r in range(l+2, n+1):
        for u in range(n-1):
            for d in range(u+2, n+1):
                point = cum[r][d] - cum[l][d] - cum[r][u] + cum[l][u]
                if point == k:
                    minarea = min(minarea, (xlist[r-1] - xlist[l]) * (ylist[d-1] - ylist[u]))
print(minarea)

Solution (Python):
import sys
from collections import deque
import copy
 
from math import *
 
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline
 
def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] =  [long(input_raw[0]), long(input_raw[1])]
    x_list = [0 for i in range(N)]
    y_list = [0 for i in range(N)]
    point_set = set([])
    for i in range(N):
        input_raw = read_func().strip().split()
        [x, y] =  [long(input_raw[0]), long(input_raw[1])]
        x_list[i] = x
        y_list[i] = y
        point_set.add((x, y))
    h = {}
    gx = {}
    gy = {}
    for x in x_list:
        for y in y_list:
            num = 0
            num_gx = 0
            num_gy = 0
            for i in range(N):
                if x <= x_list[i] and y <= y_list[i]:
                    num += 1
                if x == x_list[i] and y <= y_list[i]:
                    num_gx += 1
                if y == y_list[i] and x <= x_list[i]:
                    num_gy += 1
            h[(x, y)] = num
            gx[(x, y)] = num_gx
            gy[(y, x)] = num_gy













 
 
    min_S = long(sys.maxint) * long(sys.maxint)
    for i in range(N):
        for j in range(i + 1, N):
            for m in range(N):
                for n in range(m + 1, N):
                    x1 = min(x_list[i], x_list[j])
                    x2 = max(x_list[i], x_list[j])
                    y1 = min(y_list[m], y_list[n])
                    y2 = max(y_list[m], y_list[n])
                    in_num =  (h[(x1, y1)] - h[(x2, y1)] - h[(x1, y2)] + h[(x2, y2)] +
                                gx[(x2, y1)] - gx[(x2, y2)] + gy[(y2, x1)] - gy[(y2, x2)] +
                                  (1 if (x2, y2) in point_set else 0))









                    if in_num >= K:
                        S= abs(x1 - x2) * abs(y1 - y2)
                        if S < min_S:
                            min_S = S
    print min_S
 
 
 
if __name__ == '__main__':
    main()

Solution (Python):

def solve(N, K, XYs):
    ans = 10 ** 19 + 1

    XYs.sort(key=lambda x: x[0])
    for i in range(N):
        for j in range(i+K-1, N):
            narrowedXY = XYs[i:j+1]
            narrowedXY.sort(key=lambda x: x[1])
            for y1 in range(len(narrowedXY)):
                for y2 in range(y1+K, len(narrowedXY)+1):
                    min_x = XYs[i][0]
                    max_x = XYs[j][0]
                    ys = [xy[1] for xy in narrowedXY[y1:y2]]
                    max_y = max(ys)
                    min_y = min(ys)
                    ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))

    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    return


def B():
    return


def C():
    def bfs(a,b):
        bfs_map = [1 for i in range(n)]
        bfs_map[0] = 0
        q = deque()
        q.append(0)
        s = 1
        while q:
            x = q.pop()
            for y in v[x]:
                if [x,y] != [a,b] and [x,y] != [b,a]:
                    if bfs_map[y]:
                        bfs_map[y] = 0
                        q.append(y)
                        s += 1
        return s
    n,m = LI()
    v = [deque() for i in range(n)]
    l = deque()
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        l.append([a,b])
    ans = 0
    for a,b in l:
        s = bfs(a,b)
        if s < n:
            ans += 1
    print(ans)

def D():
    n,k = LI()
    v = [None for i in range(n)]
    for i in range(n):
        v[i] = LI()
        v[i] = [[None,None]]+[v[i]]
    v.sort(key = lambda x:x[1][1])
    for i in range(n):
        v[i][0][1] = i
    v.sort(key = lambda x:x[1][0])
    for i in range(n):
        v[i][0][0] = i
    po = [[None for i in range(n)] for j in range(n)]
    h = [None for i in range(n)]
    w = [None for i in range(n)]
    for i in range(n):
        po[v[i][0][0]][v[i][0][1]] = v[i][1]
        h[v[i][0][0]] = v[i][1][0]
        w[v[i][0][1]] = v[i][1][1]
    re = [[[[0 for x in range(n)] for y in range(n)] for t in range(n)] for s in range(n)]
    ans = float("inf")
    for s in range(n):
        for t in range(n):
            for y in range(s,n):
                for x in range(t,n):
                    if x == t:
                        re[s][t][y][x] = re[s][t][y-1][x]
                    else:
                        re[s][t][y][x] = max(0,re[s][t][y][x-1]+re[s][t][y-1][x]-re[s][t][y-1][x-1])
                    if po[y][x] != None:
                        re[s][t][y][x] += 1
                    if re[s][t][y][x] >= k:
                        ans = min(ans,(h[y]-h[s])*(w[x]-w[t]))
    print(ans)

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

Solution (Python):
n,k=map(int,input().split())
XY=[list(map(int,input().split())) for _ in range(n)]
XY.sort()
ans=float('inf')
for i in range(n):
    for j in range(i+1,n):
        x=XY[j][0]-XY[i][0]
        T=sorted(Z[1] for Z in XY[i:j+1])
        for u,v in zip(T,T[k-1:]):
            ans=min(ans,x*(v-u))
print(ans)

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

answer = 10**100
sortx = sorted(lst, key = lambda x: x[0])
for a, pt1 in enumerate(sortx[:n-k+1]):
    for b, pt2 in enumerate(sortx[a+k-1:]):
        
        sorty = sorted(sortx[a:a+k+b], key = lambda x: x[1])
        sorty_len = len(sorty)
        for c, pt3 in enumerate(sorty[:sorty_len-k+1]):
            
            pt4 = sorty[c+k-1]
            
            if pt3[1] <= pt1[1] and pt3[1] <= pt2[1] and pt4[1] >= pt1[1] and pt4[1] >= pt2[1]:
                answer = min(answer, (pt2[0] - pt1[0]) * (pt4[1] - pt3[1]))
print(answer)

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

xlst = []
ylst = []

for x,y in XY:
    x += 10**9 + 1
    y += 10**9 + 1
    xlst.append(x)
    ylst.append(y)

xset = sorted(list(set(xlst)))
yset = sorted(list(set(ylst)))



S = [ [0]*(N+1) for _ in range(N+1)]

for x,y in zip(xlst,ylst):
    x=xset.index(x)+1
    y=yset.index(y)+1
    S[y][x] = 1

for y in range(N+1):
    for x in range(1, N+1):
        S[y][x] += S[y][x-1]
for x in range(N+1):
    for y in range(1,N+1):
        S[y][x] += S[y-1][x]


ans = float("inf")
for i in range(N):
    for j in range(N):
        for k in range(N):
            for ll in range(N):

                left     = xlst[i]
                right    = xlst[j]
                top      = ylst[k]
                bottom   = ylst[ll]

                if right <= left: continue
                if bottom <= top: continue

                left = xset.index(left)+1
                right = xset.index(right)+1
                top = yset.index(top)+1
                bottom=yset.index(bottom)+1


                cnt = 0
                cnt += S[bottom][right]
                
                cnt += S[top-1][left-1]
                
                cnt -= S[top-1][right]
                
                cnt -= S[bottom][left-1]
                
                if cnt >= K:
                    left = xset[left    -1 ]
                    right = xset[right  -1 ]
                    top = yset[top      -1 ]
                    bottom = yset[bottom-1 ]
                    rect_area = (right-left)*(bottom-top)
                    ans = min(ans, rect_area)
                
print(ans)

Solution (Python):

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

points=[tuple(map(int,input().split())) for i in range(N)]
answer=10**19
sortx=sorted(points)
numberx = list(enumerate(sortx))


for left,(x1,y1) in numberx[:N-K+1]:
  
  for right,(x2,y2) in numberx[left+K-1:]:
    dx=x2-x1
    
    sorty=sorted(y for x,y in sortx[left:right+1])
    
    for y3,y4 in zip(sorty,sorty[K-1:]):
      if y3<=y1 and y3<=y2 and y4>=y1 and y4>=y2:
        answer=min(answer,dx*(y4-y3))
         
print(answer)